Maths › Further Pure 2 › The Euclidean algorithm and Bézout's identity
The Euclidean algorithm and Bézout's identity
The Euclidean algorithm finds the highest common factor of two integers by repeated division with remainder. Running the working backwards writes that factor as a combination of the original numbers, which is Bézout's identity.
Builds on The structure of proof and Induction: divisibility.
IN THIS TOPIC
- State the division theorem and run the Euclidean algorithm to a highest common factor.
- Back substitute to express the highest common factor as an integer combination, and write down the whole family of integer solutions.
- Recognise when two numbers are coprime, and say what that permits.
- Use the fact that a common divisor divides every integer combination, and apply Euclid's lemma.
- State the fundamental theorem of arithmetic and say what its uniqueness rests on.
- Write an integer in a base other than ten, and convert between bases.
COMMON MISCONCEPTION
Finding the highest common factor of two large numbers means factorising both into primes.
The Euclidean algorithm finds it with no factorisation at all. Divide, keep the remainder, replace the pair (a, b) by (b, r) and go again; the remainders strictly decrease, so the process stops, and the last non-zero remainder is the highest common factor. That is what makes it practical for numbers far too large to factorise.
Divide and keep the remainder
The division theorem says that for integers a and b with b positive, there are unique q and r with a = bq + r and 0 ≤ r < b. The Euclidean algorithm applies it over and over. Replace the pair (a, b) with (b, r) and go again. Remainders strictly decrease, so the process has to stop, and the last non-zero remainder is the highest common factor.
No factorisation happens anywhere, and that is what makes the method practical for numbers far too large to factorise. Finding the prime factorisations first works in principle and fails completely in practice.
WORKED EXAMPLE
The algorithm, then backwards
Find the highest common factor of 1071 and 462, and write it as 1071x + 462y for integers x and y.
1071 = 2 × 462 + 147; 462 = 3 × 147 + 21; 147 = 7 × 21 + 0. The last non-zero remainder is 21.
Back substitute: 21 = 462 − 3 × 147, and 147 = 1071 − 2 × 462.
So 21 = 462 − 3(1071 − 2 × 462) = 7 × 462 − 3 × 1071, giving x = −3, y = 7. Checking, −3213 + 3234 = 21.
Writing the factor as ax + by
That last step generalises. Bézout's identity says the highest common factor of a and b can always be written as ax + by for some integers x and y, and back substitution through the Euclidean working finds one such pair.
The pair is not unique. If d = gcd(a, b) divides c and (x₀, y₀) solves ax + by = c, then all integer solutions are x = x₀ + (b/d)t, y = y₀ − (a/d)t, where t ∈ Z. Taking c = d gives every Bézout pair for the highest common factor itself.
When the highest common factor is 1 the numbers are coprime, and Bézout reads ax + by = 1. Reduce that modulo b and you get ax ≡ 1, so x is the multiplicative inverse of a modulo b. Modular division rests entirely on this, so the algorithm reappears the moment congruence equations arrive.
GUIDED PRACTICE
A smaller pair
Use the Euclidean algorithm to find the highest common factor of 240 and 46, and express it in Bézout form.
Show the working
240 = 5 × 46 + 10; 46 = 4 × 10 + 6; 10 = 1 × 6 + 4; 6 = 1 × 4 + 2; 4 = 2 × 2 + 0, so the highest common factor is 2.
Back substituting: 2 = 6 − 4 = 6 − (10 − 6) = 2 × 6 − 10 = 2(46 − 4 × 10) − 10 = 2 × 46 − 9 × 10, and 10 = 240 − 5 × 46.
So 2 = 2 × 46 − 9(240 − 5 × 46) = 47 × 46 − 9 × 240. Check: 2162 − 2160 = 2.
What a common divisor divides
Write a | b to say that a divides b with nothing left over. If a | b and a | c then a | (bx + cy) for any integers x and y, since b = am and c = an turn bx + cy into a(mx + ny). A common divisor of two numbers divides every integer combination of them, and that is why the Euclidean algorithm works: each remainder is a combination of the two numbers on the line above, so the common divisors of the pair survive unchanged all the way down.
It also tests for a common factor without any factorising. Build a combination of the two numbers that cancels whatever they have in common, and whatever divides both has to divide what is left.
Bézout sharpens the same idea into Euclid's lemma: if a divides rs and a is coprime to r, then a divides s. Coprimality supplies integers x and y with ax + ry = 1, and multiplying through by s gives asx + rsy = s. The first term carries a factor of a, and so does the second since a divides rs, so a divides their sum, which is s. Drop the coprimality and the lemma goes with it, because 6 divides 4 × 3 while dividing neither 4 nor 3.
WORKED EXAMPLE
Coprime, whatever n is
Show that 3n + 1 and 4n + 1 are coprime for every integer n, and deduce that if 3n + 1 divides (4n + 1)m then it divides m.
Let d divide both. Then d divides 4(3n + 1) − 3(4n + 1) = 1, so d = 1 and the two numbers are coprime.
The combination was built to eliminate n: multiply each number by the other's coefficient of n and subtract.
For the second part, 3n + 1 divides the product (4n + 1)m and is coprime to 4n + 1, so Euclid's lemma gives 3n + 1 dividing m.
At n = 5 that reads: 16 and 21 share no factor, and 16 divides 21m only when 16 divides m.
The lemma is what makes factorising into primes unambiguous. The fundamental theorem of arithmetic says that an integer greater than 1 is a product of primes, in one way only apart from the order of the factors. Existence is a short induction and uniqueness leans on the lemma, since a prime dividing a product has to divide one of the factors. This course asks for the theorem to be known rather than proved.
Uniqueness is also what licenses reading a highest common factor off two prime factorisations, taking the lower power of each shared prime. That method is correct, but for large numbers it is far slower than the algorithm at the top of this lesson.
INDEPENDENT PRACTICE
Another coprime pair
Show that 2n + 3 and 3n + 4 are coprime for every integer n.
Show the working
Let d divide both. Then d divides 3(2n + 3) − 2(3n + 4) = 9 − 8 = 1, so d = 1 and the two are coprime.
Pick the multipliers to eliminate n, which here means 3 and 2, the swapped coefficients of n.
Spot check at n = 7: the numbers are 17 and 25, which share no factor.
The same theorem, in another base
Place value is a second job for the division theorem, and the ten in it is a habit rather than a necessity. Writing 3542 means 3 × 10³ + 5 × 10² + 4 × 10 + 2, and the argument would run the same over any base b above 1: an integer becomes a sum of multiples of the powers of b, with each digit somewhere from 0 to b − 1. The subscript notation records which base is meant, so 13220₇ stands for 1 × 7⁴ + 3 × 7³ + 2 × 7² + 2 × 7 + 0.
Reading such a number back into base ten is that sum. Going the other way is the division theorem applied over and over, as the algorithm at the top of this lesson was: divide by b and write down the remainder, then divide the quotient by b and write down that remainder, until the quotient is 0. The remainders come out in the order of the place values, so they are read upwards, and the quotients strictly decrease, so the working stops.
Above base ten the digits run out, and the letters A to F stand for 10 to 15, which covers the bases up to sixteen. Bases sixteen and two are linked: since 16 = 2⁴, each base sixteen digit becomes exactly four binary digits, and a number moves between those two bases by grouping in fours rather than by dividing at all.
The divisibility tests of the next lesson move with the base as well. A base ten number is a multiple of 10 when it ends in 0, and for the same reason a base 7 number is a multiple of 7 when it ends in 0, since every place value above the units carries a factor of the base.
WORKED EXAMPLE
One number, three bases
Write 3542 in base 7 and in base 16, and turn the second answer into binary.
Base 7 by repeated division: 3542 = 7 × 506 + 0; 506 = 7 × 72 + 2; 72 = 7 × 10 + 2; 10 = 7 × 1 + 3; 1 = 7 × 0 + 1.
Reading the remainders upwards gives 13220₇. Checking, 2401 + 1029 + 98 + 14 = 3542.
Base 16 the same way: 3542 = 16 × 221 + 6; 221 = 16 × 13 + 13; 13 = 16 × 0 + 13. The remainder 13 is the digit D, so the answer is DD6₁₆, and 13 × 256 + 13 × 16 + 6 = 3542.
Each base sixteen digit is four binary digits, and D is 1101 while 6 is 0110, so the number is 110111010110₂. The place values 2048, 1024, 256, 128, 64, 16, 4 and 2 add back to 3542.
GUIDED PRACTICE
Which base is it?
Write 2401 in base 7. Then, given that 2013 in some base n stands for 1035 in base ten, find n.
Show the working
2401 = 7⁴, so the digits are a 1 followed by four zeros: 10000₇.
For the second, the digits 2, 0, 1 and 3 stand for 2n³ + 0n² + 1n + 3, so 2n³ + n + 3 = 1035, that is 2n³ + n = 1032.
A digit of 3 puts n above 3, and trying values from there gives n = 8, since 2 × 512 + 8 = 1032.
Checking from the other side: 1035 = 8 × 129 + 3; 129 = 8 × 16 + 1; 16 = 8 × 2 + 0; 2 = 8 × 0 + 2, and the remainders read upwards give 2013.
ASSESSMENT FOCUS
- Set the divisions out one per line, because the back substitution then reads straight up the page.
- Stop at the last non-zero remainder, and say which line it came from.
- In back substitution, replace one remainder at a time and never expand prematurely.
- Check the Bézout coefficients by substituting back. The arithmetic is quick and the signs are easy to lose.
- To show two expressions are coprime, combine them so that the variable cancels and 1 is left; any common divisor then divides 1.
- Name Euclid's lemma when you use it, and say which factor the divisor is coprime to. Without that coprimality the conclusion does not follow.
- Converting to another base, read the remainders upwards, and check by expanding the place values back into base ten.
- Write the base as a subscript on every answer that is not in base ten, since 110 in base 2 and 110 in base ten are different numbers.
CHECK YOURSELF
Use the Euclidean algorithm to find the highest common factor of 84 and 30.
Show a hint
Divide, keep the remainder, repeat.
Show the answer
84 = 2 × 30 + 24; 30 = 1 × 24 + 6; 24 = 4 × 6 + 0. The highest common factor is 6.
Euclid: divide, keep the remainder, repeat, and the last non-zero remainder is the highest common factor; the same repeated division, carried on the quotient, writes a number in any base.
Bézout: back substitution writes that factor as ax + by, and when it is 1 the coefficient x inverts a modulo b. With d = gcd(a, b) and one solution (x₀, y₀) of ax + by = c, all integer solutions are x = x₀ + (b/d)t, y = y₀ − (a/d)t for t ∈ Z.
A common divisor of b and c divides bx + cy; Euclid's lemma: if a divides rs and a is coprime to r then a divides s.
Fundamental theorem: an integer above 1 is a product of primes in one way only, up to order.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the Euclidean algorithm and Bézout's identity questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- State the division theorem and run the Euclidean algorithm to a highest common factor.
- Back substitute to express the highest common factor as an integer combination, and write down the whole family of integer solutions.
- Recognise when two numbers are coprime, and say what that permits.
- Use the fact that a common divisor divides every integer combination, and apply Euclid's lemma.
- State the fundamental theorem of arithmetic and say what its uniqueness rests on.
- Write an integer in a base other than ten, and convert between bases.
Open the full revision checklist to see every objective in the course in one place.