Divisibility and the division algorithm

Number theory studies the integers \(\ldots, -2, -1, 0, 1, 2, \ldots\) and especially the positive integers, the numbers we count with. It is one of the oldest branches of mathematics. Euclid's Elements, written around 300 BCE, already contains the Euclidean algorithm, the infinitude of the primes and a formula for even perfect numbers, and some of the problems that occupied Fermat, Euler and Gauss are still being worked on today. Number theory is famous for questions that a child can understand but that took centuries to answer, such as Fermat's claim that \(x^n + y^n = z^n\) has no solutions in positive integers for \(n \ge 3\), proved by Andrew Wiles in 1995, and for questions still open, such as Goldbach's conjecture that every even number greater than 2 is a sum of two primes.

For a long time number theory was admired precisely because it seemed useless. G. H. Hardy wrote in 1940 that nobody had yet found a warlike purpose for it. Within forty years that had changed completely. The security of online banking, messaging and software updates now rests on facts about primes and modular arithmetic that this course develops: Fermat's little theorem, Euler's theorem, primitive roots and the difficulty of factoring large numbers. The final lesson puts these together into the RSA and Diffie–Hellman systems. Along the way we will meet one of the most beautiful theorems in all of mathematics, Gauss's law of quadratic reciprocity.

This course assumes the proof techniques of MATH-228: direct proof, contradiction, contrapositive and induction. Number theory is an excellent place to put them into practice, because the objects are concrete and every claim can be tested on examples, by hand or by computer, before it is proved. Each lesson includes a short Python program for exactly that purpose. Python's integers have no size limit, so the programs work just as well with 300-digit numbers as with small ones.

Divisibility

Definition. Let \(a\) and \(b\) be integers. We say \(a\) divides \(b\), and write \(a \mid b\), if there is an integer \(k\) with \(b = ak\). We then also say that \(a\) is a divisor or factor of \(b\), and that \(b\) is a multiple of \(a\). If \(a\) does not divide \(b\) we write \(a \nmid b\).

For example \(3 \mid 12\) because \(12 = 3 \cdot 4\), \(-5 \mid 35\) because \(35 = (-5)(-7)\), and \(4 \nmid 14\) because no integer \(k\) satisfies \(4k = 14\). Note that \(a \mid b\) is a statement, true or false, not a number: \(3 \mid 12\) is true, whereas \(12/3\) is the number 4. Mixing the two up is a common source of confusion. Some edge cases are worth recording. Every integer divides 0, since \(0 = a \cdot 0\). The only integer that 0 divides is 0 itself. The numbers 1 and \(-1\) divide every integer, and every integer \(a\) is divisible by \(\pm 1\) and \(\pm a\).

Divisibility depends only on absolute values: \(a \mid b\) if and only if \(|a|\) divides \(|b|\). For that reason we usually concentrate on positive divisors. The positive divisors of 12 are 1, 2, 3, 4, 6 and 12; the positive divisors of 17 are just 1 and 17.

Basic properties

Theorem. For all integers \(a, b, c, x, y\):

• If \(a \mid b\) and \(b \mid c\), then \(a \mid c\) (transitivity).

• If \(a \mid b\) and \(a \mid c\), then \(a \mid bx + cy\) (linear combinations).

• If \(a \mid b\) and \(b \ne 0\), then \(|a| \le |b|\).

• If \(a \mid b\) and \(b \mid a\), then \(a = \pm b\).

Proof. For transitivity, write \(b = ak\) and \(c = bl\). Then \(c = a(kl)\), and \(kl\) is an integer. For linear combinations, write \(b = ak\) and \(c = al\); then \(bx + cy = a(kx + ly)\). For the size bound, \(b = ak\) with \(b \ne 0\) forces \(k \ne 0\), so \(|k| \ge 1\) and \(|b| = |a||k| \ge |a|\). Finally, if \(a \mid b\) and \(b \mid a\) and both are nonzero, the size bound gives \(|a| \le |b| \le |a|\), so \(|a| = |b|\); if one of them is 0, the other is 0 too, since 0 divides only 0.

The linear combination property is used constantly. Here is a typical application: if \(d\) divides both \(n\) and \(n + 1\), then \(d\) divides \((n + 1) - n = 1\), so \(d = \pm 1\). Consecutive integers have no common factor larger than 1. Similarly, if \(d \mid 3n + 5\) and \(d \mid 2n + 3\), then \(d\) divides \(2(3n + 5) - 3(2n + 3) = 1\). These small tricks are the seed of the Euclidean algorithm in the next lesson.

The division algorithm

Most pairs of integers do not divide one another, but we can always divide with a remainder. This is the most important basic fact in elementary number theory.

Theorem (division algorithm). Let \(a\) and \(b\) be integers with \(b > 0\). There are unique integers \(q\) and \(r\) such that \[a = qb + r \quad\text{and}\quad 0 \le r < b.\] The number \(q\) is the quotient and \(r\) is the remainder of \(a\) on division by \(b\).

The figure shows the idea: \(qb\) is the largest multiple of \(b\) that does not exceed \(a\), and \(r\) is the gap between them. Turning that picture into a proof needs the well-ordering principle, the axiom that every nonempty set of nonnegative integers has a least element.

Proof of existence. Consider the set \(S = \{a - kb : k \in \mathbb{Z},\ a - kb \ge 0\}\). It is nonempty: taking \(k = -|a|\) gives \(a + |a|b \ge a + |a| \ge 0\), because \(b \ge 1\). By well-ordering, \(S\) has a least element \(r = a - qb\). Certainly \(r \ge 0\). If \(r \ge b\), then \(r - b = a - (q + 1)b\) would be a smaller element of \(S\), a contradiction. So \(0 \le r < b\).

Proof of uniqueness. Suppose \(a = qb + r = q'b + r'\) with \(0 \le r, r' < b\). Then \(b(q - q') = r' - r\), so \(b\) divides \(r' - r\). But \(-b < r' - r < b\), and the only multiple of \(b\) strictly between \(-b\) and \(b\) is 0. Hence \(r = r'\), and then \(q = q'\).

The remainder is always nonnegative, even when \(a\) is negative. Dividing \(-17\) by 5 gives \(-17 = (-4)\cdot 5 + 3\), with remainder 3, not \(-2\). In terms of the floor function, \(q = \lfloor a/b \rfloor\) and \(r = a - b\lfloor a/b \rfloor\). Python's operators // and % follow exactly this convention for a positive divisor, so (-17) // 5 is -4 and (-17) % 5 is 3. Some other programming languages truncate toward zero instead and would give \(-3\) and \(-2\); that difference has caused many bugs.

Finally, \(b \mid a\) if and only if the remainder of \(a\) on division by \(b\) is 0. So the division algorithm gives a mechanical test for divisibility, and it shows that every integer has exactly one of the forms \(bq, bq + 1, \ldots, bq + (b - 1)\).

Proofs by cases on the remainder

Because every integer leaves one of only \(b\) possible remainders on division by \(b\), many statements can be proved by checking \(b\) cases.

Claim: the square of every integer has the form \(4k\) or \(4k + 1\). Proof: an integer is even, \(n = 2m\), or odd, \(n = 2m + 1\). In the first case \(n^2 = 4m^2\). In the second \(n^2 = 4m^2 + 4m + 1 = 4(m^2 + m) + 1\). Consequence: no integer of the form \(4k + 3\) is a sum of two squares, since a sum of two squares leaves remainder 0, 1 or 2 on division by 4. So 3, 7, 11, 15 and 19 are not sums of two squares, and neither is 1,000,003. Lesson 9 returns to the question of which numbers are sums of two squares.

Claim: every odd square has the form \(8k + 1\). Proof: \(n = 2m + 1\) gives \(n^2 = 4m(m + 1) + 1\), and one of the consecutive integers \(m, m + 1\) is even, so \(8 \mid 4m(m + 1)\). For instance \(9 = 8 + 1\), \(25 = 3 \cdot 8 + 1\), \(49 = 6 \cdot 8 + 1\).

Claim: the product of any three consecutive integers is divisible by 6. Proof: among \(n, n + 1, n + 2\), one is even, and one is a multiple of 3, because the three remainders on division by 3 are 0, 1, 2 in some order. So both 2 and 3 divide the product, and since 2 and 3 have no common factor, so does 6. (That last step uses a fact we prove properly in lesson 3: if two numbers with no common factor both divide \(N\), so does their product.)

Even and odd, and the parity argument

The case \(b = 2\) deserves special attention: every integer is even, \(2k\), or odd, \(2k + 1\), and not both. Parity arguments solve puzzles that look hard. A classic one: can a chessboard with two opposite corners removed be tiled by dominoes? Each domino covers one light and one dark square, but the two removed corners are the same shade, leaving 30 squares of one shade and 32 of the other, so the answer is no. Parity also shows that \(\sqrt 2\) is irrational: if \(p^2 = 2q^2\) with \(p/q\) in lowest terms, then \(p^2\) is even, so \(p\) is even, so \(4 \mid 2q^2\) and \(q\) is even too, contradicting lowest terms.

Writing numbers in a base

Repeated use of the division algorithm gives the representation of a number in any base. Theorem: if \(b \ge 2\), every positive integer \(n\) can be written uniquely as \[n = d_kb^k + d_{k-1}b^{k-1} + \cdots + d_1b + d_0, \qquad 0 \le d_i < b,\ d_k \ne 0.\]

To find the digits, divide \(n\) by \(b\): the remainder is \(d_0\). Divide the quotient by \(b\): the remainder is \(d_1\). Continue until the quotient is 0. For example, in base 2: \(45 = 22 \cdot 2 + 1\), \(22 = 11 \cdot 2 + 0\), \(11 = 5 \cdot 2 + 1\), \(5 = 2 \cdot 2 + 1\), \(2 = 1 \cdot 2 + 0\), \(1 = 0 \cdot 2 + 1\). Reading the remainders from the bottom up, \(45 = 101101_2\). Existence follows by strong induction on \(n\), since the quotient is smaller than \(n\); uniqueness follows from the uniqueness of the remainder at each step.

Base representations explain the familiar divisibility rules. Since \(10 = 9 + 1\), every power \(10^k\) leaves remainder 1 on division by 9, so \(n = \sum d_i10^i\) and its digit sum \(\sum d_i\) differ by a multiple of 9: precisely, \(n - \sum d_i = \sum d_i(10^i - 1)\), and \(9 \mid 10^i - 1\) because \(10^i - 1 = 99\ldots9\). Hence \(n\) is divisible by 9, or by 3, exactly when its digit sum is. Since \(10 = 11 - 1\), the powers of 10 alternate between remainders 1 and 10 on division by 11, which gives the alternating digit sum test for 11: \(11 \mid 918{,}082\) because \(2 - 8 + 0 - 8 + 1 - 9 = -22\). Lesson 4 will make these arguments one-liners with the language of congruences.

Base 2 is the language of computers, and base 16 (hexadecimal) packs four binary digits into one symbol. The fast exponentiation algorithm of lesson 6, which makes modern cryptography practical, works by reading the exponent in binary.

Divisibility by computer

The program checks the division algorithm on several pairs, including negative dividends, converts numbers between bases by repeated division, lists the divisors of a number by trial up to its square root, and tests the claim that odd squares leave remainder 1 on division by 8.

def divide(a, b):
    """Return (q, r) with a = q*b + r and 0 <= r < b, for b > 0."""
    q, r = a // b, a % b
    assert a == q * b + r and 0 <= r < b
    return q, r

for a, b in [(30, 7), (-17, 5), (100, 9), (-1, 4)]:
    q, r = divide(a, b)
    print(f"{a} = {q}*{b} + {r}")

def to_base(n, b):
    digits = []
    while n > 0:
        n, d = divmod(n, b)
        digits.append("0123456789abcdef"[d])
    return "".join(reversed(digits)) or "0"

print("45 in base 2:", to_base(45, 2), " check:", int(to_base(45, 2), 2))
print("2026 in base 16:", to_base(2026, 16), " in base 7:", to_base(2026, 7))

def divisors(n):
    small, large = [], []
    d = 1
    while d * d <= n:
        if n % d == 0:
            small.append(d)
            if d * d != n:
                large.append(n // d)
        d += 1
    return small + large[::-1]

print("divisors of 360:", divisors(360), "count:", len(divisors(360)))
print("odd squares mod 8:", sorted({(2 * m + 1) ** 2 % 8 for m in range(1000)}))
print("digit sum test for 9:", all((n % 9 == 0) == (sum(map(int, str(n))) % 9 == 0) for n in range(1, 10000)))

30 = 4*7 + 2
-17 = -4*5 + 3
100 = 11*9 + 1
-1 = -1*4 + 3
45 in base 2: 101101  check: 45
2026 in base 16: 7ea  in base 7: 5623
divisors of 360: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360] count: 24
odd squares mod 8: [1]
digit sum test for 9: True

The divisor routine only tries \(d\) up to \(\sqrt n\), because divisors come in pairs \(d\) and \(n/d\), one of which is at most \(\sqrt n\). That observation reduces the work of finding all divisors of a number near a million from a million trial divisions to a thousand. The last two lines check theorems from this lesson on thousands of cases. A check like this is evidence, never a proof, but it is an excellent way to catch a false conjecture before trying to prove it.