Discrete Mathematics and Proof

The Euclidean algorithm and coprime numbers

Factoring a large number can take thousands of trial divisions. Is there a way to find the largest number dividing two integers without ever factoring either one?

You need

Greatest common factor and least common multipleGrades 5 to 6 Modular arithmeticGrades 10 to 12

Unlocks

Bezout's identity and the extended Euclidean algorithmDiscrete Mathematics and Proof

Where you are 8 in Introductory number theory

Logic, proof and discrete math6

Introductory number theory8

▴ 2 above The division algorithm Numbers in other bases

The Euclidean algorithm and coprime numbers

Bezout's identity and the extended Euclidean algorithm There are infinitely many primes ▾ Show all 8 (1 more)

When you reach for it

Reach for the Euclidean algorithm whenever you need the largest integer dividing two given integers, or need to know whether two integers share any factor at all. For small numbers you can list the factors (Greatest common factor by listing) or compare prime factorizations (Finding them from prime factorizations). Both need the factors first, and finding factors is slow.

Ksenija wants the greatest common divisor of 4757 and 3763. To factor 4757 she would try the primes 2, 3, 5, 7, \dots in turn; the first that works is 67, the nineteenth prime, giving 4757 = 67 \cdot 71. A second search gives 3763 = 53 \cdot 71, so the answer is 71. The Euclidean algorithm reaches 71 in six divisions and never learns that 67 or 53 exist (Example 1). The gap grows with the numbers: for two 100-digit numbers the algorithm needs at most a few hundred divisions, while factoring numbers of that size by trial division is out of reach.

The procedure

Greatest common divisor. Let a and b be integers, not both zero. A common divisor of a and b is an integer d with d \mid a and d \mid b. The greatest common divisor \gcd(a, b) is the largest of them. It exists: 1 is always a common divisor, and if, say, a \ne 0, every common divisor has |d| \le |a| by the size bound of Divisibility as a relation, so there are finitely many. Hence \gcd(a, b) \ge 1. Since d \mid a exactly when d \mid -a, signs do not matter: \gcd(a, b) = \gcd(|a|, |b|), and clearly \gcd(a, b) = \gcd(b, a).

Every integer divides 0, so the common divisors of a and 0 are just the divisors of a, and

\gcd(a, 0) = |a| \quad \text{for } a \ne 0.

For a = b = 0 every integer is a common divisor and there is no largest, so \gcd(0, 0) is not defined.

Coprime. Integers a and b are coprime, or relatively prime, when \gcd(a, b) = 1: their only common divisors are 1 and -1. Neither needs to be prime: 8 and 15 are coprime.

The key lemma. If a = bq + r for integers a, b, q, r, then a, b and b, r have exactly the same common divisors. So if a and b are not both zero, \gcd(a, b) = \gcd(b, r).

Proof. Let d be a common divisor of a and b. Then d divides a - bq = r, because a divisor of two integers divides every combination ax + by (Proving statements about divisibility). So d is a common divisor of b and r. Conversely, if d \mid b and d \mid r, then d divides bq + r = a, so d is a common divisor of a and b. The two sets of common divisors are equal. If b and r were both zero, then a = 0 too; so when a, b are not both zero, neither are b, r, both greatest common divisors are defined, and as the largest elements of equal sets they are equal. \square

Nothing in the lemma asks r to be a remainder, or q to be a quotient. Any integer q works, which is what makes the lemma useful in proofs (Examples 3 to 5).

The algorithm. Take a and b with b > 0 (replace each by its absolute value first; if one is 0, the formula above already gives the answer). By The division algorithm, write a = bq_1 + r_1 with 0 \le r_1 < b. If r_1 = 0, then \gcd(a, b) = \gcd(b, 0) = b and you are done. Otherwise divide b by r_1, getting b = r_1 q_2 + r_2 with 0 \le r_2 < r_1, and keep going: each new division divides the last divisor by the last remainder.

Why it stops: the remainders satisfy b > r_1 > r_2 > r_3 > \cdots \ge 0. A strictly decreasing list of nonnegative integers cannot go on forever (it has at most b terms below b), so some remainder r_n is followed by r_{n+1} = 0. Why the answer is right: the lemma, applied at every division, gives

\begin{aligned} \gcd(a, b) &= \gcd(b, r_1) = \gcd(r_1, r_2) = \cdots \\ &= \gcd(r_n, 0) = r_n. \end{aligned}

The greatest common divisor is the last nonzero remainder.

A picture. Cut as many b by b squares as fit from an a by b rectangle; the strip left over is r_1 by b. Cut squares of side r_1 from that strip, and so on. The last squares have side \gcd(a, b), and they tile the whole rectangle, since each larger square side is a multiple of the next.

Figure 1The algorithm on 26 and 10 as geometry. Each division cuts off as many squares as fit; the last, smallest squares have side 2 = \gcd(26, 10), and squares of that size tile the whole rectangle.

How fast. Two divisions in a row always at least halve a remainder (Example 7). So after 2k divisions the remainder is below \displaystyle \frac{b}{2^k}. For b < 10^{100} < 2^{333} this forces a zero remainder by division 666. The slowest inputs, where every quotient but the last is 1, are consecutive Fibonacci numbers.

Worked examples

Example 1

Ksenija’s pair

Find \gcd(4757, 3763).

Solution

Divide, then divide the divisor by the remainder, until a remainder is 0:

\begin{aligned} 4757 &= 1 \cdot 3763 + 994 \\ 3763 &= 3 \cdot 994 + 781 \\ 994 &= 1 \cdot 781 + 213 \\ 781 &= 3 \cdot 213 + 142 \\ 213 &= 1 \cdot 142 + 71 \\ 142 &= 2 \cdot 71 + 0 \end{aligned}

Each line is the division algorithm, with the remainder less than the divisor. By the lemma, \gcd(4757, 3763) = \gcd(3763, 994), and so on down to \gcd(71, 0) = 71. The last nonzero remainder is 71, found in six divisions. Check: 4757 = 67 \cdot 71 and 3763 = 53 \cdot 71, and 67 and 53 are different primes, so nothing larger than 71 divides both.

Example 2

Signs, zero and order

Find (a) \gcd(-391, 299), (b) \gcd(299, 391), (c) \gcd(-560, 0).

Solution

(a) Signs do not matter, so this is \gcd(391, 299):

\begin{aligned} 391 &= 1 \cdot 299 + 92 \\ 299 &= 3 \cdot 92 + 23 \\ 92 &= 4 \cdot 23 + 0 \end{aligned}

The answer is 23.

(b) Starting with the smaller number costs one extra division and nothing else: 299 = 0 \cdot 391 + 299 just swaps the pair, and the steps of (a) follow. Again 23.

Example 3

Consecutive integers are coprime

Prove that \gcd(n, n + 1) = 1 for every integer n.

Solution

Proof. The integers n and n + 1 are never both zero. Since n + 1 = 1 \cdot n + 1, the lemma with q = 1 gives \gcd(n + 1, n) = \gcd(n, 1). The only positive divisor of 1 is 1, so \gcd(n, 1) = 1. \square

In words: a common divisor of n and n + 1 divides their difference 1.

Example 4

A coprime pair for every n

Prove that \gcd(5n + 2, 3n + 1) = 1 for every integer n.

Solution

Proof. Apply the lemma three times, each time subtracting a multiple of the smaller-looking expression:

\begin{aligned} 5n + 2 &= 1 \cdot (3n + 1) + (2n + 1) \\ 3n + 1 &= 1 \cdot (2n + 1) + n \\ 2n + 1 &= 2 \cdot n + 1 \end{aligned}

\begin{aligned} \gcd(5n + 2, 3n + 1) &= \gcd(3n + 1, 2n + 1) \\ &= \gcd(2n + 1, n) \\ &= \gcd(n, 1) = 1. \end{aligned}

The pair 5n + 2, 3n + 1 is never 0, 0, since 3n + 1 = 0 has no integer solution. \square

These “remainders” are expressions, and for negative n they may even be negative. That is allowed, because the lemma holds for any integer q. For n = 4: \gcd(22, 13) = 1.

Example 5

A gcd that depends on n

For which integers n is \gcd(4n + 3, n + 2) greater than 1, and what is it then?

Solution

The number 4n + 3 is odd, so never 0. Since 4n + 3 = 4(n + 2) - 5, the lemma with q = 4 and r = -5 gives

\begin{aligned} \gcd(4n + 3, n + 2) &= \gcd(n + 2, -5) \\ &= \gcd(n + 2, 5). \end{aligned}

The positive divisors of 5 are 1 and 5, so the gcd is 5 when 5 \mid n + 2 and 1 otherwise. Now 5 \mid n + 2 means n + 2 = 5j for some integer j, that is, n = 5k + 3 with k = j - 1. So the gcd is 5 exactly when n = 5k + 3 for some integer k, and 1 for every other n. Check: n = 3 gives \gcd(15, 5) = 5, and n = 0 gives \gcd(3, 2) = 1.

Example 6

The largest square tile

A rectangular floor measures 216 by 156 inches. What is the largest square tile, with side a whole number of inches, that covers it exactly with no cutting, and how many tiles does it take?

Solution

A square tile of side s fits a whole number of times along both edges exactly when s \mid 216 and s \mid 156. So the largest tile has side \gcd(216, 156):

\begin{aligned} 216 &= 1 \cdot 156 + 60 \\ 156 &= 2 \cdot 60 + 36 \\ 60 &= 1 \cdot 36 + 24 \\ 36 &= 1 \cdot 24 + 12 \\ 24 &= 2 \cdot 12 + 0 \end{aligned}

The tile is 12 inches on a side. Along the edges fit \displaystyle \frac{216}{12} = 18 and \displaystyle \frac{156}{12} = 13 tiles, so the floor takes 18 \cdot 13 = 234 tiles. Each division is one stage of the squares picture: one 156-inch square, then two of side 60, and so on.

Example 7

Two divisions halve a remainder

In the algorithm, r_{k+2} is the remainder when r_k is divided by r_{k+1} (with r_0 = b). Prove that \displaystyle r_{k+2} < \frac{r_k}{2}, and conclude that for 0 < b \le 1000 the algorithm on a and b uses at most 20 divisions.

Solution

Proof. Two cases. If \displaystyle r_{k+1} \le \frac{r_k}{2}, then \displaystyle r_{k+2} < r_{k+1} \le \frac{r_k}{2}, since a remainder is less than its divisor. If instead \displaystyle r_{k+1} > \frac{r_k}{2}, then r_{k+1} goes into r_k exactly once with something left: r_k = 1 \cdot r_{k+1} + (r_k - r_{k+1}), and 0 \le r_k - r_{k+1} < r_{k+1}. By the uniqueness in the division algorithm this is the division, so

r_{k+2} = r_k - r_{k+1} < r_k - \tfrac{r_k}{2} = \tfrac{r_k}{2}. \qquad \square

Applying this repeatedly from r_0 = b gives \displaystyle r_{2j} < \frac{b}{2^j}. With b \le 1000 < 1024 = 2^{10}, the remainder r_{20}, if the algorithm gets that far, is below 1, so it is 0. Hence at most 20 divisions. The true worst case is smaller: a computer search over all 1000 \ge a > b \ge 1 finds at most 14 divisions, reached by the consecutive Fibonacci numbers 987 and 610.

Boundaries

Not both zero. \gcd(0, 0) is undefined, since every integer divides 0. With one zero, \gcd(a, 0) = |a|.
The lemma needs any q; stopping needs the true remainder. Any q keeps the gcd, but only 0 \le r < b forces the numbers to shrink. With q = 0, a = 0 \cdot b + a just swaps the pair, and swapping forever never ends.
It finds the gcd, not the factors. The algorithm says 71 divides both numbers in Example 1, but nothing about whether 71 is prime or what the other factors are.
Coprime is about a pair. For three integers, \gcd(6, 10, 15) = 1 (no integer above 1 divides all three), yet no two of them are coprime. “Pairwise coprime” is the stronger condition.

Where this goes next

Running the divisions backward writes \gcd(a, b) as ax + by for integers x, y; that is Bezout’s identity and the Bezout's identity and the extended Euclidean algorithm, which also gives Euclid’s lemma and, from it, the uniqueness in the fundamental-theorem-of-arithmetic. Coprimality decides when a number has an inverse in Modular arithmetic, written with Congruence modulo n and its arithmetic. The pair 5n + 3, 3n + 2, shown coprime in Proving statements about divisibility by guessing a combination, falls to the lemma in a few lines, with no guessing.

Exercises

Running the algorithm

Find \gcd(1517, 1271).
Find \gcd(2431, 1001).
Find (a) \gcd(-84, -120), (b) \gcd(-858, 0), (c) \gcd(0, 45). Why is \gcd(0, 0) not defined?
Find \gcd(851, 703) and count the divisions.
Run the algorithm on 233 and 144. How many divisions does it take, and what do you notice about the remainders and quotients?
Without doing any division, explain why 1729 and 4096 = 2^{12} are coprime.

Coprime pairs and the lemma

Prove that two consecutive odd integers 2n + 1 and 2n + 3 are coprime.
Prove that \gcd(8n + 5, 5n + 3) = 1 for every integer n.
For which integers n is \gcd(2n + 7, n + 1) > 1? What is it then?
Prove that n and n^2 + 1 are coprime for every integer n.
Find every possible value of \gcd(n^2 + 3n + 5, n + 1), and say which n give each.

Squares and steps

A floor is 210 by 165 inches. Find the largest square tile with a whole-number side that covers it exactly, and the number of tiles.
Cut a 19 by 7 rectangle into squares as in the figure. List the squares, check that their areas add to 133, and read off \gcd(19, 7).
Show that the algorithm on 89 and 55 takes 9 divisions. Then use Example 7 to show that when 0 < b \le 100 no run takes more than 14.

Reasoning and proof

Prove that every common divisor of a and b divides \gcd(a, b).
Refute with a counterexample: “If a and b are coprime and b and c are coprime, then a and c are coprime.”
Explain why the algorithm on a and b > 0 takes at most b divisions. Show that this bound is reached for b = 3 but not for b = 5.
Prove that n! + 1 and (n + 1)! + 1 are coprime for every positive integer n.
Prove that two different primes are coprime, and give two coprime integers, both greater than 1, neither of which is prime.

Answers

41. 1517 = 1 \cdot 1271 + 246, 1271 = 5 \cdot 246 + 41, 246 = 6 \cdot 41 + 0.
143. 2431 = 2 \cdot 1001 + 429, 1001 = 2 \cdot 429 + 143, 429 = 3 \cdot 143 + 0.
(a) 12: it is \gcd(120, 84), and 120 = 1 \cdot 84 + 36, 84 = 2 \cdot 36 + 12, 36 = 3 \cdot 12. (b) 858. (c) 45. Every integer divides 0, so 0 and 0 have infinitely many common divisors and no largest one.
37, in four divisions: 851 = 1 \cdot 703 + 148, 703 = 4 \cdot 148 + 111, 148 = 1 \cdot 111 + 37, 111 = 3 \cdot 37 + 0.
Eleven divisions, and the gcd is 1. The remainders are 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 0, each the difference of the two before it, and every quotient is 1 except the last, 2 = 2 \cdot 1 + 0. These are Fibonacci numbers, the slowest case.
The positive divisors of 2^{12} are the powers 1, 2, 4, \dots, 2^{12}. Every one except 1 is even, and 1729 is odd, so the only positive common divisor is 1.
Proof. 2n + 3 = 1 \cdot (2n + 1) + 2 and 2n + 1 = n \cdot 2 + 1, so the gcd is \gcd(2n + 1, 2) = \gcd(2, 1) = 1. (Neither number is ever 0.) \square
Proof. 8n + 5 = 1 \cdot (5n + 3) + (3n + 2), 5n + 3 = 1 \cdot (3n + 2) + (2n + 1), 3n + 2 = 1 \cdot (2n + 1) + (n + 1), 2n + 1 = 1 \cdot (n + 1) + n, n + 1 = 1 \cdot n + 1. So the gcd equals \gcd(n, 1) = 1; and 8n + 5 is odd, so never 0. \square
2n + 7 = 2(n + 1) + 5, so the gcd is \gcd(n + 1, 5). It is 5 exactly when n = 5k + 4 for some integer k, and 1 otherwise. For n = 4: \gcd(15, 5) = 5.
Proof. n^2 + 1 = n \cdot n + 1, so \gcd(n^2 + 1, n) = \gcd(n, 1) = 1, and n^2 + 1 \ne 0. \square
1 or 3. Since n^2 + 3n + 5 = (n + 2)(n + 1) + 3, the gcd is \gcd(n + 1, 3): it is 3 when n = 3k + 2 for some integer k (for example n = 2 gives \gcd(15, 3) = 3), and 1 for every other n.
Side 15 inches, 154 tiles. 210 = 1 \cdot 165 + 45, 165 = 3 \cdot 45 + 30, 45 = 1 \cdot 30 + 15, 30 = 2 \cdot 15. Along the edges fit 14 and 11 tiles, and 14 \cdot 11 = 154.
Two squares of side 7, one of side 5, two of side 2, two of side 1, from 19 = 2 \cdot 7 + 5, 7 = 1 \cdot 5 + 2, 5 = 2 \cdot 2 + 1, 2 = 2 \cdot 1. Areas: 98 + 25 + 8 + 2 = 133. So \gcd(19, 7) = 1.
Remainders 34, 21, 13, 8, 5, 3, 2, 1, 0: nine divisions. For the bound, b \le 100 < 128 = 2^7, so \displaystyle r_{14} < \frac{b}{2^7} < 1, and r_{14} = 0 if reached.
Proof. If b = 0, a common divisor d divides a, hence |a| = \gcd(a, 0); similarly if a = 0. Otherwise run the algorithm on |a| and |b|, which have the same common divisors as a and b. By the lemma each division keeps the set of common divisors, so the common divisors of a, b are those of r_n and 0, which are the divisors of r_n = \gcd(a, b). \square
a = 2, b = 3, c = 4: \gcd(2, 3) = 1 and \gcd(3, 4) = 1, but \gcd(2, 4) = 2.
The remainders r_1 > r_2 > \cdots > r_{n+1} = 0 are different integers from 0, 1, \dots, b - 1, so there are at most b of them, one per division. For b = 3: 5 = 1 \cdot 3 + 2, 3 = 1 \cdot 2 + 1, 2 = 2 \cdot 1 + 0, three divisions. For b = 5 the first remainder r_1 is one of 0, 1, 2, 3, 4, and the rest of the run is the run on 5 and r_1, which takes at most 3 divisions (the worst is r_1 = 3). So at most 4, for example \gcd(8, 5).
Proof. (n + 1)! + 1 = (n + 1)(n! + 1) - n, so the gcd is \gcd(n! + 1, -n) = \gcd(n! + 1, n). Since n \ge 1, n! + 1 = (n - 1)! \cdot n + 1, so this is \gcd(n, 1) = 1. \square
Proof. Let p \ne q be primes. The positive divisors of p are 1 and p, and p \nmid q because the positive divisors of q are 1 and q, and p is neither. So the only positive common divisor is 1. \square Example: 9 and 16, since 16 = 1 \cdot 9 + 7, 9 = 1 \cdot 7 + 2, 7 = 3 \cdot 2 + 1, 2 = 2 \cdot 1.