Two pages of a ninth-century Greek manuscript of Euclid's Elements, with a geometric figure drawn in the text
Unit 02 · All masterclasses · 60 min

Divisibility and the Euclidean Algorithm

Division with remainder, the greatest common divisor, and the oldest algorithm still in use
Image: Biblioteca Apostolica Vaticana, Vat. gr. 190, via Wikimedia Commons

Division with remainder is the first theorem of number theory, and this unit shows how much follows from it: positional notation in any base, Euclid's algorithm for the greatest common divisor with Lamé's bound on its running time, Bézout's identity and the extended algorithm that finds its coefficients, and the complete solution of the linear Diophantine equation ax + by = c. The same algorithm computes the inverses that every public-key cryptosystem needs.

Preview: the beginning of the unit

Dividing 30 by 7 and keeping the remainder 2 looks like the smallest piece of arithmetic there is. This unit shows how far it carries. Division with remainder is where the unit begins, and from it follow the notation in which computers store numbers, the oldest algorithm still in daily use, and a method for solving equations in integers that the software behind many digital signatures runs every time it signs.

1 Divisibility

Let \(a\) and \(b\) be integers. We say that \(a\) divides \(b\), and write \(a \mid b\), if there is an integer \(k\) with \(b = ak\). Then \(a\) is called a divisor of \(b\), and \(b\) a multiple of \(a\). When no such \(k\) exists we write \(a \nmid b\). For example, \(7 \mid 42\) because \(42 = 7 \cdot 6\), and \(7 \nmid 40\) because 40 lies strictly between the multiples \(35\) and \(42\) of 7. Negative numbers are allowed on both sides, so \(-3 \mid 12\) and \(3 \mid -12\), and the divisors of 12 are \(\pm1, \pm2, \pm3, \pm4, \pm6, \pm12\).

Each rule is proved in one line from the definition. For rule 1, write \(b = ak\) and \(c = bl\), so that \(c = a(kl)\). For rule 2, write \(b = ak\) and \(c = al\), so that \(bx + cy = a(kx + ly)\). For rule 3, write \(b = ak\) with \(k \neq 0\), which gives \(|b| = |a|\,|k| \ge |a|\). For rule 4, when \(a\) and \(b\) are both non-zero, rule 3 applied in both directions gives \(|a| \le |b|\) and \(|b| \le |a|\), so \(|a| = |b|\) and \(a = \pm b\); if one of them is 0, the other must be 0 too, because 0 is the only multiple of 0.

Two special cases deserve a moment. Every integer \(a\) divides 0, because \(0 = a \cdot 0\), and 1 divides every integer. On the other hand \(0 \mid b\) holds only for \(b = 0\), since \(0 \cdot k\) is always 0. The definition says nothing about fractions, and it should not be read as “\(b/a\) is an integer” when \(a = 0\).

Rule 2 is at work whenever two known multiples are combined. If \(a \mid b\) and \(a \mid c\), then \(a\) divides \(b + c\) and \(b - c\); for example, 3 divides \(999\) and \(99\), so it divides \(999 + 99 = 1098\) and \(999 - 99 = 900\) without any further calculation. Such rules will be used without comment from now on.

The full unit is part of the program

Want to see a complete unit first? Unit 3, Prime Numbers and Unique Factorization, is free to read.