Divisibility and the Euclidean algorithm

Finding the largest number that divides both $6188$ and $4709$ by factoring them means discovering that $4709 = 17 \times 277$ , and factoring is slow work that gets slower very quickly as numbers grow.

The previous lesson closed the counting half of the course; this one opens the second half, on the structure of the integers. Recall that $a ∣ b$ means $b = a k$ for some integer $k$ , and that a number dividing $b$ and $c$ divides every combination $b x + c y$ . This lesson proves that division leaves a well defined remainder, turns that into Euclid's algorithm for the greatest common divisor, which needs no factoring, shows why it is fast, and runs it backwards.

Division with remainder

Dividing $17$ by $5$ gives $3$ with remainder $2$ , and school arithmetic takes for granted that the answer always exists and is the only one. Both halves need proof, because everything here rests on them.

The division algorithm. For integers $a$ and $b$ with $b > 0$ there are unique integers $q$ and $r$ with $a = b q + r$ and $0 \leq r < b$ . The number $q$ is the quotient and $r$ the remainder, written $a mod b$ .

For existence, let $S$ be the set of non-negative numbers of the form $a - b k$ , with $k$ any integer. It is not empty, since $k = - | a |$ gives $a + b | a | \geq 0$ . The well-ordering principle, that every non-empty set of non-negative integers has a least element, is induction in another form, and it gives a smallest member of $S$ , say $r = a - b q$ . Then $r \geq 0$ . If $r \geq b$ , then $r - b = a - b (q + 1)$ would be a smaller member of $S$ , which is impossible. So $0 \leq r < b$ .

For uniqueness, suppose $a = b q + r = b q^{'} + r^{'}$ with both remainders between $0$ and $b - 1$ . Then $b (q - q^{'}) = r^{'} - r$ , which lies strictly between $- b$ and $b$ . The only multiple of $b$ there is $0$ , so $r = r^{'}$ and $q = q^{'}$ .

The condition $0 \leq r < b$ matters for negative $a$ : $- 17 = 5 \times (- 4) + 3$ , so $- 17 mod 5 = 3$ . Programming languages often disagree. In C and JavaScript -17 % 5 gives $- 2$ , because they round the quotient towards zero, and code that assumes remainders are never negative breaks on exactly this case.

The greatest common divisor

For integers $a$ and $b$ , not both zero, the greatest common divisor $\gcd (a, b)$ is the largest integer dividing both. It exists because $1$ is a common divisor and no divisor of a non-zero number exceeds its size. So $\gcd (12, 18) = 6$ , $\gcd (8, 15) = 1$ , and $\gcd (a, 0) = | a |$ , since every integer divides $0$ . Numbers whose $\gcd$ is $1$ are coprime.

Listing divisors fails for large numbers, and factoring first only moves the difficulty, since no fast method of factoring is known; a later lesson rests a whole cryptosystem on that fact. The way round it is one observation about remainders.

The key lemma. If $a = b q + r$ for integers $q$ and $r$ , then $a$ and $b$ have exactly the same common divisors as $b$ and $r$ . In particular $\gcd (a, b) = \gcd (b, r)$ .

The proof is divisibility of combinations and nothing else. If $d ∣ a$ and $d ∣ b$ , then $d$ divides $a - b q$ , which is $r$ . If $d ∣ b$ and $d ∣ r$ , then $d$ divides $b q + r$ , which is $a$ . So the two pairs share one set of common divisors, and one set has one largest member. The lemma does not need $r$ to be the remainder, or even positive; any $q$ will do, a freedom used below.

With $r = a mod b$ it reads $\gcd (a, b) = \gcd (b, a mod b)$ , and it replaces a pair by a strictly smaller one, since $a mod b < b$ .

Euclid's algorithm

Apply the lemma over and over. Divide $a$ by $b$ , divide $b$ by the remainder, and keep dividing each divisor by the remainder it left, until a remainder is $0$ . The last non-zero remainder $g$ is the greatest common divisor: the final pair is $(g, 0)$ , $\gcd (g, 0) = g$ , and the lemma says the $\gcd$ never changed on the way. The process stops because the remainders are a strictly decreasing sequence of non-negative integers.

This is Propositions 1 and 2 of Book VII of Euclid's Elements, written around 300 BC. Euclid works with lengths, taking the smaller from the larger until it no longer fits, which is division done by repeated subtraction. Donald Knuth called it the granddaddy of all algorithms, the oldest nontrivial one still in use, and it still runs inside the software that reduces fractions and generates encryption keys.

Example. Find $\gcd (6188, 4709)$ .

Each row divides $a$ by $b$ , and the next row moves $b$ and the remainder up one place:

$a$	$b$	quotient	remainder
$6188$	$4709$	$1$	$1479$
$4709$	$1479$	$3$	$272$
$1479$	$272$	$5$	$119$
$272$	$119$	$2$	$34$
$119$	$34$	$3$	$17$
$34$	$17$	$2$	$0$

The last non-zero remainder is $17$ , so $\gcd (6188, 4709) = 17$ , after six divisions and without meeting the prime $277$ . Check: $6188 = 17 \times 364$ and $4709 = 17 \times 277$ , and since $277$ is prime and does not divide $364$ , nothing larger is shared.

Now you. Find $\gcd (5767, 4453)$ , and count the divisions.

Answer

$5767 = 1 \times 4453 + 1314$ , $4453 = 3 \times 1314 + 511$ , $1314 = 2 \times 511 + 292$ , $511 = 1 \times 292 + 219$ , $292 = 1 \times 219 + 73$ , $219 = 3 \times 73 + 0$ . Six divisions, and $\gcd (5767, 4453) = 73$ . Check: $5767 = 73 \times 79$ and $4453 = 73 \times 61$ .

Euclid on symbols

The algorithm does not need numbers. Whenever one expression is a multiple of another plus something simpler, the lemma applies, and a question about infinitely many pairs becomes a few lines of algebra.

Example. Prove that $\frac{21 n + 4}{14 n + 3}$ is in lowest terms for every positive integer $n$ . This was the first problem of the first International Mathematical Olympiad, held in Romania in 1959.

Lowest terms means the $\gcd$ of top and bottom is $1$ . Divide as if the expressions were numbers: $21 n + 4 = 1 \times (14 n + 3) + (7 n + 1)$ and $14 n + 3 = 2 \times (7 n + 1) + 1$ . By the lemma twice, $\gcd (21 n + 4, 14 n + 3) = \gcd (14 n + 3, 7 n + 1) = \gcd (7 n + 1, 1) = 1$ . At $n = 7$ the fraction is $\frac{151}{101}$ , and both are prime.

Now you. Show that $\gcd (n + 3, 2 n + 1)$ is always $1$ or $5$ , and say for which $n$ it is $5$ .

Answer

Write $2 n + 1 = 2 (n + 3) - 5$ . The lemma allows any quotient, so $\gcd (2 n + 1, n + 3) = \gcd (n + 3, - 5) = \gcd (n + 3, 5)$ , which is $1$ or $5$ . It is $5$ exactly when $5 ∣ n + 3$ , that is for $n = 2, 7, 12, \dots$ ; at $n = 7$ the pair is $10$ and $15$ .

Why it is fast

Six divisions for four digit numbers is typical, and there is a quick reason. If a remainder is at most half the divisor before it, the next is smaller still; if it is more than half, the next quotient is $1$ and the next remainder is the difference, less than half. Either way every two divisions at least halve the numbers, so the work grows with the number of digits, not with the size of the numbers.

The exact worst case was found by Gabriel Lamé in 1844, and it is the Fibonacci numbers, $F_{0} = 0$ , $F_{1} = 1$ and $F_{n} = F_{n - 1} + F_{n - 2}$ , the sequence that earlier lessons on recurrences solved with Binet's formula. Run the algorithm on $F_{n + 2}$ and $F_{n + 1}$ . Since $F_{n + 2} = 1 \times F_{n + 1} + F_{n}$ with $F_{n} < F_{n + 1}$ , every quotient is $1$ and every remainder is the previous Fibonacci number, until $(3, 2)$ leaves $1$ and $(2, 1)$ finishes with quotient $2$ . That is exactly $n$ divisions, shrinking as slowly as possible, and it ends at $1$ : consecutive Fibonacci numbers are coprime.

Lamé's theorem. If the algorithm on $a > b > 0$ takes $n$ divisions, then $b \geq F_{n + 1}$ and $a \geq F_{n + 2}$ .

Read the run from the bottom up. The last non-zero remainder is at least $1 = F_{2}$ . The number above it is a larger multiple of it, so at least $2 = F_{3}$ . Every other number is the one below it times a quotient of at least $1$ , plus the one below that, so it is at least the sum of the two. That is the Fibonacci recurrence with $\geq$ in place of $=$ , and induction up the run gives the bounds $F_{4}, F_{5}, \dots$ , reaching $F_{n + 1}$ at $b$ and $F_{n + 2}$ at $a$ . Consecutive Fibonacci numbers meet every bound exactly, so no smaller pair takes as long.

The counts check out. The pair $(144, 89) = (F_{12}, F_{11})$ takes $10$ divisions, and a computer search over every pair with $b < 100$ finds nothing longer; with $b < 1000$ the longest run is $15$ , at $(1597, 987)$ . Binet's formula makes $F_{n + 1}$ grow like ${1.618}^{n}$ , and ${1.618}^{5} \approx 11.09$ exceeds $10$ , so each extra digit of $b$ allows fewer than five more divisions: at most five times the number of digits of $b$ . For a $100$ digit $b$ the true maximum is $479$ , since $F_{480}$ is the largest Fibonacci number below $10^{100}$ .

Running it backwards

Each division can be solved for its remainder, and that makes the $\gcd$ more than the largest common divisor: it is a combination of the two numbers.

Bézout's identity. For integers $a$ and $b$ , not both zero, there are integers $x$ and $y$ with $a x + b y = \gcd (a, b)$ .

The proof is the algorithm. The first two numbers of the run are combinations of $a$ and $b$ , trivially: $a = 1 \times a + 0 \times b$ and $b = 0 \times a + 1 \times b$ . Each later number is the one two places above minus a quotient times the one just above, and that is again a combination. By induction every remainder is a combination of $a$ and $b$ , the last non-zero one included. The name is Étienne Bézout's, for his 1779 work on polynomials, though Claude Bachet de Méziriac stated the integer version in 1624.

A computer carries $x$ and $y$ forwards like this, row by row. By hand it is easier to start at the bottom and substitute upwards, which is why the method, called extended Euclid, is described as running the algorithm backwards.

Example. Find integers $x$ and $y$ with $252 x + 198 y = \gcd (252, 198)$ .

The run is $252 = 1 \times 198 + 54$ , $198 = 3 \times 54 + 36$ , $54 = 1 \times 36 + 18$ and $36 = 2 \times 18$ , so the $\gcd$ is $18$ . Solve the last useful division for $18$ , then replace each remainder by the division that produced it:

18 = 54 - 36 = 54 - (198 - 3 \times 54) = 4 \times 54 - 198

4 \times 54 - 198 = 4 (252 - 198) - 198 = 4 \times 252 - 5 \times 198

So $x = 4$ and $y = - 5$ . Check: $1008 - 990 = 18$ .

Now you. Find integers $x$ and $y$ with $97 x + 35 y = 1$ .

Answer

The run is $97 = 2 \times 35 + 27$ , $35 = 1 \times 27 + 8$ , $27 = 3 \times 8 + 3$ , $8 = 2 \times 3 + 2$ , $3 = 1 \times 2 + 1$ , so the $\gcd$ is $1$ . Substituting upwards, $1 = 3 - 2 = 3 \times 3 - 8 = 3 \times 27 - 10 \times 8 = 13 \times 27 - 10 \times 35 = 13 \times 97 - 36 \times 35$ . So $x = 13$ and $y = - 36$ , and indeed $1261 - 1260 = 1$ .

What Bézout's identity buys

Write $g = \gcd (a, b) = a x + b y$ . Any common divisor $d$ divides $a x + b y$ , so $d ∣ g$ : the $\gcd$ is greatest in the stronger sense that every common divisor divides it. The common divisors of $252$ and $198$ are exactly the divisors of $18$ .

It also settles which numbers are combinations. Since $g$ divides $a$ and $b$ , it divides every $a x + b y$ , and scaling the Bézout combination gives every multiple of $g$ . So $a x + b y = c$ has integer solutions exactly when $g ∣ c$ , and the smallest positive combination is $g$ itself. For instance $252 x + 198 y = 36$ is solved by $x = 8$ , $y = - 10$ , while $252 x + 198 y = 30$ has no solution, since $18$ does not divide $30$ . Solutions are never unique: adding $11$ to $x$ and subtracting $14$ from $y$ changes $252 x + 198 y$ by $2772 - 2772 = 0$ , so $(15, - 19)$ also gives $18$ .

In particular $a$ and $b$ are coprime exactly when $1$ is a combination of them, since a common divisor of both divides any combination. A later lesson builds division in modular arithmetic on exactly this.

Its first real consequence, though, is about primes. A divisor of a product need not divide a factor: $6$ divides $36 = 4 \times 9$ but divides neither $4$ nor $9$ . For a prime it must, and a prime $p$ that does not divide $a$ is coprime to it, so $p x + a y = 1$ for some integers, which is the lever. That is Euclid's lemma, Proposition 30 of the same Book VII, and the next lesson proves it from Bézout's identity in three lines and builds on it the fundamental theorem of arithmetic: every integer greater than $1$ factors into primes in exactly one way.