On this page
Finding the gcd of two numbers is the easy half. The harder question, common in number theory and remainder problems, is how to write that gcd as a combination of the two numbers. You always can, by running the Euclidean algorithm forwards and then backwards. Here is the full method on one example, with a check and the formula for every other answer.
What does Bézout's identity say?
Bézout's identity: if a and b are integers with greatest common divisor d, then there exist integers x and y such that ax + by = d (Wikipedia: Bézout's identity; Wolfram MathWorld). The numbers of the form az + bt are exactly the multiples of d, so d is the smallest positive one.
It is named after Étienne Bézout (1730–1783), who proved it for polynomials; the statement for integers appears earlier in the work of Claude Gaspard Bachet de Méziriac (1581–1638), according to the same article. The algorithm underneath is far older: Book VII, Proposition 2 of Euclid's Elements sets out "to find the greatest common measure of two given numbers not relatively prime" (Euclid's Elements, Clark University edition). For the plain HCF method first, read our post on Euclid's division algorithm for finding the HCF.
How do you find x and y with the extended Euclidean algorithm?
The extended Euclidean algorithm computes the gcd of a and b and, at the same time, the coefficients x and y (Wikipedia: Extended Euclidean algorithm). By hand it has three stages. Take a = 252 and b = 198.
Stage 1, divide down to the gcd:
252 = 1 × 198 + 54
198 = 3 × 54 + 36
54 = 1 × 36 + 18
36 = 2 × 18 + 0
The last non-zero remainder is 18, so gcd(252, 198) = 18.
Stage 2, rewrite each line as "remainder = ...":
54 = 252 − 1 × 198
36 = 198 − 3 × 54
18 = 54 − 1 × 36
Stage 3, substitute from the bottom up:
Start with the gcd line: 18 = 54 − 36.
Replace 36: 18 = 54 − (198 − 3 × 54) = 4 × 54 − 198.
Replace 54: 18 = 4 × (252 − 198) − 198 = 4 × 252 − 5 × 198.
So x = 4 and y = −5. Check: 1008 − 990 = 18.
Is there only one pair x, y?
No. Once you have one pair (x, y), every pair is (x − k·b/d, y + k·a/d) for any integer k (Wikipedia: Bézout's identity).
Here b/d = 11 and a/d = 14, so all the answers are x = 4 − 11k and y = −5 + 14k. With k = 1 you get (−7, 9), and indeed −1764 + 1782 = 18. In the diagram at the top, these pairs are the whole-number points on the line 252x + 198y = 18.
Why does writing gcd as ax + by matter?
The case to know is when a and b are coprime, so ax + by = 1. Then x is the multiplicative inverse of a modulo b, and computing that inverse is an essential step in making RSA encryption keys (Wikipedia: Extended Euclidean algorithm).
A short example: find the inverse of 7 modulo 40.
40 = 5 × 7 + 5, then 7 = 1 × 5 + 2, then 5 = 2 × 2 + 1, so the gcd is 1.
1 = 5 − 2 × 2 = 5 − 2 × (7 − 5) = 3 × 5 − 2 × 7.
1 = 3 × (40 − 5 × 7) − 2 × 7 = 3 × 40 − 17 × 7.
So the inverse is −17 + 40 = 23. Check: 7 × 23 = 161 = 4 × 40 + 1. The same toolkit sits behind finding remainders of large powers and counting numbers coprime to n.
How do you write it up in an exam?
Write every division on its own line as a = q × b + r, and stop at remainder 0.
Rewrite each line as r = a − q × b before substituting.
Substitute from the bottom up, one remainder per line, with brackets.
Multiply out at the end to check.
If the question wants a different pair (say x positive), use x − k·b/d and y + k·a/d.
To practise on fresh pairs, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. If divisibility itself feels shaky, the Fermi Concept Library gives each mathematics concept its own lesson.
Try it now on 161 and 28: you should find gcd 7, then check your x and y by multiplying out.
