Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 37 · Getting Started

Integers and the Division Algorithm

Learn the integers, the well-ordering principle and the division algorithm a = bq + r, including how Python's // and % treat negative numbers.

The integers are the numbers ... −3, −2, −1, 0, 1, 2, 3 ... with the symbol ℤ. You can add, subtract and multiply any two of them and stay inside ℤ, but division is different: 7 divided by 2 is not an integer. Number theory lives in that gap. Instead of giving up, we keep both pieces of the answer: how many whole times 2 fits into 7 (three times) and what is left over (one).

That idea is formalized by the division algorithm, the single most used fact in the whole course. In this lesson you will state it precisely, see why it is true, and learn how Python's // and % handle negative numbers, because getting the signs right is where many bugs begin.

Natural numbers and the well-ordering principle

The natural numbers are 1, 2, 3, ... (some books include 0). They have a property that looks obvious but is powerful: every non-empty set of natural numbers has a smallest element. This is the well-ordering principle. It fails for the integers (negatives go on forever) and for positive fractions (1/2, 1/3, 1/4 ... has no smallest member), which is why it is special.

Proofs use it like this: to show something exists, collect all the candidates in a set, and the smallest candidate is the one you want. The division algorithm is proved exactly this way.

The division algorithm

Theorem. For every integer a and every positive integer b there are unique integers q and r with a = b·q + r and 0 ≤ r < b.

The number q is the quotient, r is the remainder, a is the dividend and b is the divisor. The condition 0 ≤ r < b is what makes the pair unique: without it, 7 = 2·2 + 3 would be allowed too.

Why it is true. Look at the set S of all non-negative numbers of the form a − b·k for integers k. It is not empty (take k very negative if a is negative, or k = 0 if a ≥ 0), so by well-ordering it has a smallest element, call it r = a − b·q. If r ≥ b, then r − b = a − b(q + 1) would be a smaller member of S, a contradiction. So 0 ≤ r < b. If two pairs (q, r) and (q', r') both worked, then b(q − q') = r' − r, a multiple of b of absolute value less than b, which forces it to be 0. That gives uniqueness.

Python Quotient and remainder

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Negative numbers

For a positive divisor, the algorithm still gives a non-negative remainder when the dividend is negative. Take a = −7 and b = 2. We need −7 = 2q + r with 0 ≤ r < 2. Choose q = −4: 2 · (−4) = −8, and −7 − (−8) = 1. So −7 = 2·(−4) + 1, quotient −4 and remainder 1. A calculator that says "quotient −3, remainder −1" is using a different convention (truncation towards zero).

Python follows the mathematical convention: // is floor division, and % always takes the sign of the divisor. Many other languages (C, Java, JavaScript) truncate towards zero, so -7 % 2 is -1 there. When a divisor is positive, Python's result is exactly the remainder of the algorithm.

Python Floor division and negatives

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Never assume % is non-negative in other languages. In C, Java and JavaScript, -7 % 2 is -1. When you port number-theory code, write ((a % b) + b) % b.

Divisors and multiples

Say that b divides a, written b | a, when the remainder is 0, so a = b·k for some integer k. Then b is a divisor (or factor) of a and a is a multiple of b. Every integer divides 0, and 1 divides everything. The next lesson on divisibility builds a toolbox around this definition; here you only need the link: b | a exactly when a mod b = 0.

You can use the algorithm to classify numbers. With b = 2 every integer is of the form 2q or 2q + 1 (even or odd). With b = 3 there are three families: 3q, 3q + 1 and 3q + 2. This case split by remainder is one of the most common proof techniques. For example, a perfect square is always of the form 3k or 3k + 1: if n = 3q then n² = 9q²; if n = 3q ± 1 then n² = 9q² ± 6q + 1 = 3(3q² ± 2q) + 1.

Python Squares mod 3 and mod 4

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Squares leave remainders {0, 1} when divided by 3 or 4 and {0, 1, 4} when divided by 8. That tiny observation is useful: it quickly shows, for example, that no square ends in the digits 2, 3, 7 or 8, and that a number of the form 4k + 3 can never be a perfect square.

Remainders as a picture

Dividing by b sorts all integers into b boxes labeled 0 to b − 1, one for each possible remainder. The boxes repeat every b steps along the number line.

flowchart LR
  A["..., -4, 0, 4, 8, ..."] --> R0["remainder 0"]
  B["..., -3, 1, 5, 9, ..."] --> R1["remainder 1"]
  C["..., -2, 2, 6, 10, ..."] --> R2["remainder 2"]
  D["..., -1, 3, 7, 11, ..."] --> R3["remainder 3"]

Division by 4 splits the integers into four classes by remainder.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Write 100 = 7q + r with 0 <= r < 7. What are q and r?

    7 * 14 = 98 and 100 - 98 = 2, with 0 <= 2 < 7.
  2. 2. What does Python give for -7 % 2?

    Python's % has the sign of the divisor, so -7 = 2 * (-4) + 1 gives remainder 1.
  3. 3. Which property makes the quotient and remainder unique?

    Requiring a remainder between 0 and b - 1 leaves exactly one choice of q.
  4. 4. Which set of natural numbers has no smallest element, showing why well-ordering needs natural numbers?

    The integers extend infinitely downward. Every non-empty set of natural numbers has a smallest element.

Summary

  • For any integer a and positive b there are unique q and r with a = bq + r and 0 ≤ r < b.
  • The proof uses the well-ordering principle on the set of non-negative values a − bk.
  • b divides a exactly when the remainder is 0.
  • Python's // and % use floor division, so the remainder is never negative for a positive divisor; other languages may differ.
  • Splitting integers by remainder is a basic proof tool, for example squares are 0 or 1 mod 3 and mod 4.

Next: Number Theory in Python