Maths › Further Pure 2 › The Euclidean algorithm and Bezout's identity
The Euclidean algorithm and Bezout's identity
Divide, keep the remainder, repeat. The last non-zero remainder is the highest common factor, and running the working backwards writes it as a combination of the two numbers you started with.
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.
- Recognise when two numbers are coprime and what that permits.
WHAT YOU PROBABLY THINK
Finding the highest common factor of two large numbers means factorising both into primes.
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 repeatedly: replace the pair (a, b) with (b, r) and go again. The remainders strictly decrease, so the process stops, and the last non-zero remainder is the highest common factor.
No factorisation is needed anywhere, which is what makes the method practical for numbers far too large to factorise: the opening claim describes a method that works in principle and fails 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. That is x = −3, y = 7, and checking: −3213 + 3234 = 21.
Bezout's identity
That last step is general. Bezout'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 them. The pair is not unique: adding a multiple of b to x and subtracting the matching multiple of a from y gives another.
When the highest common factor is 1 the numbers are coprime, and Bezout then reads ax + by = 1. Reducing that modulo b makes ax ≡ 1, so x is the multiplicative inverse of a modulo b: the identity is what makes modular division possible at all.
YOUR TURN
A smaller pair
Use the Euclidean algorithm to find the highest common factor of 240 and 46, and express it in Bezout 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.
Unwinding: 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.
THE EXAM BIT
- Set the divisions out one per line; the back substitution reads straight up the page from them.
- 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 Bezout coefficients by substituting back; the arithmetic is quick and the signs are easy to lose.
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
8
4
=
2
×
3
0
+
2
4
;
3
0
=
1
×
2
4
+
6
;
2
4
=
4
×
6
+
0
.
T
h
e
h
i
g
h
e
s
t
c
o
m
m
o
n
f
a
c
t
o
r
i
s
6
.
Euclid: divide, keep the remainder, repeat; the last non-zero remainder is the highest common factor.
Bezout: back substitution writes that factor as ax + by, and when it is 1 the coefficient x inverts a modulo b.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- 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.
- Recognise when two numbers are coprime and what that permits.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.