The extended Euclidean algorithm finds the greatest common divisor of two numbers and, at the same time, two integers x and y satisfying ax + by = gcd(a, b). For 252 and 198 it returns gcd 18 along with x = 4 and y = −5, because 4 × 252 − 5 × 198 = 1008 − 990 = 18.
The ordinary Euclidean algorithm answers “what is the gcd”. The extended version answers “and how do I build it out of the two original numbers”. Those coefficients x and y are what make modular inverses, linear Diophantine equations and RSA key generation possible.
This guide starts from the plain algorithm, then teaches both extended methods: back-substitution, which shows why it works, and the table method, which is faster and harder to get wrong. Pseudocode and eight practice problems follow.
Part 1: The Ordinary Euclidean Algorithm
The method rests on one fact:
gcd(a, b) = gcd(b, a mod b)Divide, keep the remainder, repeat with the divisor and that remainder. When a remainder hits 0, the previous remainder is the gcd.
Why it works. Any number d dividing both a and b also divides a − qb, which is exactly the remainder r. So every common divisor of (a, b) is a common divisor of (b, r), and the argument runs in reverse too. The two pairs share the same set of common divisors, so the largest one survives every step.
Why it stops. Each remainder is strictly smaller than the divisor that produced it and never goes below 0, so the sequence must reach 0 after finitely many steps.
Example: gcd(252, 198)
Write each step in the form a = q × b + r:
252 = 1 × 198 + 54
198 = 3 × 54 + 36
54 = 1 × 36 + 18
36 = 2 × 18 + 0 ← stopThe last non-zero remainder is 18, so gcd(252, 198) = 18.
Four divisions handled it. Listing the factors of both numbers would have taken far longer, and the gap grows enormously for large inputs. This is the same chain the Euclidean Algorithm Calculator prints for any pair.
Part 2: Bézout’s Identity
The extension rests on a theorem:
Bézout’s identity. For any integers a and b, not both zero, there exist integers x and y with ax + by = gcd(a, b).
Those x and y are called the Bézout coefficients. For 252 and 198 they are 4 and −5.
Three things are worth knowing about them.
They are not unique. If (x, y) works, so does (x + b/g, y − a/g) for the same g, and every other shift by that amount. For 252 and 198 with g = 18, adding 11 to x and subtracting 14 from y gives another valid pair: 15 × 252 − 19 × 198 = 3780 − 3762 = 18. ✓
At least one is usually negative. Since ax + by must come out smaller than both a and b, the two terms have to work against each other.
They exist only for the gcd. The equation ax + by = c has an integer solution if and only if gcd(a, b) divides c. So 252x + 198y = 36 is solvable, since 18 divides 36, but 252x + 198y = 25 is not.
Part 3: The Back-Substitution Method
This method runs the ordinary algorithm forward, then unwinds it. It takes longer than the table method but shows exactly where the coefficients come from.
Step 1: Run the algorithm and keep every equation
Using 252 and 198 again, rearrange each line to isolate the remainder:
252 = 1 × 198 + 54 → 54 = 252 − 1 × 198
198 = 3 × 54 + 36 → 36 = 198 − 3 × 54
54 = 1 × 36 + 18 → 18 = 54 − 1 × 36
36 = 2 × 18 + 0 (the stopping line, not used)Step 2: Start from the gcd and substitute upward
Begin with the last useful equation, the one whose remainder is the gcd:
18 = 54 − 1 × 36Replace 36 using the line above it, 36 = 198 − 3 × 54:
18 = 54 − (198 − 3 × 54)
= 54 − 198 + 3 × 54
= 4 × 54 − 198Collect terms at every stage rather than expanding everything at the end. Now replace 54 using 54 = 252 − 1 × 198:
18 = 4 × (252 − 198) − 198
= 4 × 252 − 4 × 198 − 198
= 4 × 252 − 5 × 198Step 3: Read off the coefficients
4 × 252 + (−5) × 198 = 18So x = 4 and y = −5.
Verification. 4 × 252 = 1008 and 5 × 198 = 990, and 1008 − 990 = 18. ✓
The key discipline is to never multiply out 252 or 198 into a plain number. They must stay as symbols until the very end, otherwise the coefficients disappear into the arithmetic.
Part 4: The Table Method
The table method computes the coefficients as it goes, in one forward pass. It is faster, it needs no unwinding, and it is what a computer implementation does.
Keep three columns alongside each remainder: r, x and y. Every column obeys the same recurrence, driven by the quotient q from each division:
new value = value two rows above − q × value one row aboveSeed the table with two rows that are true by inspection:
row 0: r = a, x = 1, y = 0 because a = 1·a + 0·b
row 1: r = b, x = 0, y = 1 because b = 0·a + 1·bExample: 1180 and 482
| Row | q | r | x | y |
|---|---|---|---|---|
| 0 | 1180 | 1 | 0 | |
| 1 | 482 | 0 | 1 | |
| 2 | 2 | 216 | 1 | −2 |
| 3 | 2 | 50 | −2 | 5 |
| 4 | 4 | 16 | 9 | −22 |
| 5 | 3 | 2 | −29 | 71 |
| 6 | 8 | 0 |
Working row 2: q = 1180 ÷ 482 = 2, so r = 1180 − 2 × 482 = 216, x = 1 − 2 × 0 = 1, and y = 0 − 2 × 1 = −2.
Row 3: q = 482 ÷ 216 = 2, so r = 482 − 2 × 216 = 50, x = 0 − 2 × 1 = −2, and y = 1 − 2 × (−2) = 5.
Row 4: q = 216 ÷ 50 = 4, so r = 216 − 4 × 50 = 16, x = 1 − 4 × (−2) = 9, and y = −2 − 4 × 5 = −22.
Row 5: q = 50 ÷ 16 = 3, so r = 50 − 3 × 16 = 2, x = −2 − 3 × 9 = −29, and y = 5 − 3 × (−22) = 71.
Row 6 gives a remainder of 0, so the answer is the row above it.
Answer. gcd(1180, 482) = 2, with x = −29 and y = 71.
Verification. −29 × 1180 + 71 × 482 = −34,220 + 34,222 = 2. ✓
A built-in check
Every row of the table satisfies r = a·x + b·y, not just the last one. That makes it easy to catch an error early. Checking row 4:
9 × 1180 + (−22) × 482 = 10,620 − 10,604 = 16 ✓ matches rIf a row fails this test, the mistake is in that row or the one before it, and there is no need to redo the whole table.
Part 5: Finding a Modular Inverse
This is the main application. The inverse of b modulo a exists when gcd(a, b) = 1, and the extended algorithm produces it directly.
Problem. Find the inverse of 37 modulo 120.
Run the algorithm on 120 and 37:
120 = 3 × 37 + 9
37 = 4 × 9 + 1
9 = 9 × 1 + 0 ← stopThe gcd is 1, so an inverse exists.
Back-substitute:
1 = 37 − 4 × 9
9 = 120 − 3 × 37, so substitute:
1 = 37 − 4 × (120 − 3 × 37)
= 37 − 4 × 120 + 12 × 37
= 13 × 37 − 4 × 120Read it modulo 120. The term −4 × 120 vanishes, leaving:
13 × 37 ≡ 1 (mod 120)Answer. 37⁻¹ ≡ 13 (mod 120).
Verification. 13 × 37 = 481 = 120 × 4 + 1. ✓
The general rule: after solving ax + by = 1, the coefficient y is the inverse of b modulo a. If it comes out negative, add a to bring it into the range 0 to a − 1. The other methods for finding inverses, and how to choose between them, are covered in modular inverse.
Part 6: Solving ax + by = c
Once you have a solution for the gcd, scaling gives a solution for any multiple of it.
Problem. Solve 252x + 198y = 54.
The gcd is 18, and 18 divides 54, so solutions exist. From above, 4 × 252 − 5 × 198 = 18. Multiply everything by 54 ÷ 18 = 3:
12 × 252 − 15 × 198 = 54Answer. x = 12, y = −15. Check: 3024 − 2970 = 54. ✓
The full solution set. Every solution has the form
x = 12 + (198/18)t = 12 + 11t
y = −15 − (252/18)t = −15 − 14tfor any integer t. Taking t = 1 gives x = 23 and y = −29, and 23 × 252 − 29 × 198 = 5796 − 5742 = 54. ✓
When there is no solution. 252x + 198y = 25 has none, because every value of 252x + 198y is a multiple of 18, and 25 is not.
Part 7: Pseudocode
Iterative, matching the table method:
function extended_gcd(a, b):
old_r, r = a, b
old_x, x = 1, 0
old_y, y = 0, 1
while r != 0:
q = old_r / r (integer division, rounded down)
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
old_y, y = y, old_y - q * y
return (old_r, old_x, old_y) # gcd, x, yRecursive:
function extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
(g, x1, y1) = extended_gcd(b, a mod b)
x = y1
y = x1 - (a / b) * y1
return (g, x, y)The iterative version is preferred in practice, since it uses constant memory and cannot exhaust the call stack on large inputs.
Speed. The number of divisions is at most about 5 times the number of decimal digits in the smaller input, a bound that comes from the worst case being consecutive Fibonacci numbers. Two 300 digit numbers therefore need only a few thousand divisions, which is why RSA key generation is instant.
Common Mistakes
- Multiplying out a and b during back-substitution. They must stay as symbols. Once 252 becomes a plain number, the coefficient is lost.
- Substituting downward instead of upward. Start from the equation whose remainder is the gcd and work back toward the first division.
- Using the stopping line. The equation with remainder 0 carries no information and must be left out of the substitution.
- Getting the table recurrence backwards. Each new entry is two rows above minus q times one row above, and the same q applies to all three columns.
- Dropping a sign. Negative coefficients are normal. Row 5 of the example has x = −29, and that is the answer.
- Reporting the wrong coefficient as the inverse. Solving ax + by = 1 makes y the inverse of b modulo a, and x the inverse of a modulo b.
- Leaving the inverse negative. Add the modulus to land in the range 0 to n − 1.
- Assuming ax + by = c always has a solution. It does only when gcd(a, b) divides c.
Practice Problems
For each pair, find the gcd and a pair of Bézout coefficients x and y with ax + by = gcd(a, b).
- a = 84, b = 30
- a = 161, b = 28
- a = 1035, b = 759
- a = 391, b = 299
- a = 105, b = 88
- a = 1001, b = 357
- Find the inverse of 15 modulo 26.
- Find the inverse of 17 modulo 64.
Answers
- 84 = 2 × 30 + 24, then 30 = 1 × 24 + 6, then 24 = 4 × 6 + 0. So gcd = 6, and back-substituting gives 6 = 30 − 24 = 30 − (84 − 2 × 30) = −1 × 84 + 3 × 30. Check: −84 + 90 = 6. ✓
- 161 = 5 × 28 + 21, then 28 = 1 × 21 + 7, then 21 = 3 × 7 + 0. gcd = 7, and 7 = 28 − 21 = 28 − (161 − 5 × 28) = −1 × 161 + 6 × 28. Check: −161 + 168 = 7. ✓
- 1035 = 1 × 759 + 276, then 759 = 2 × 276 + 207, then 276 = 1 × 207 + 69, then 207 = 3 × 69 + 0. gcd = 69, with x = 3, y = −4. Check: 3105 − 3036 = 69. ✓
- 391 = 1 × 299 + 92, then 299 = 3 × 92 + 23, then 92 = 4 × 23 + 0. gcd = 23, with x = −3, y = 4. Check: −1173 + 1196 = 23. ✓
- gcd = 1, with x = −31, y = 37. Check: −3255 + 3256 = 1. ✓ Since the gcd is 1, 105 and 88 are coprime.
- 1001 = 2 × 357 + 287, then 357 = 1 × 287 + 70, then 287 = 4 × 70 + 7, then 70 = 10 × 7 + 0. gcd = 7, with x = 5, y = −14. Check: 5005 − 4998 = 7. ✓
- Run the algorithm on 26 and 15: 26 = 1 × 15 + 11, then 15 = 1 × 11 + 4, then 11 = 2 × 4 + 3, then 4 = 1 × 3 + 1. The gcd is 1, and back-substitution gives −4 × 26 + 7 × 15 = 1. So the inverse of 15 modulo 26 is 7. Check: 105 = 26 × 4 + 1. ✓
- Run the algorithm on 64 and 17: 64 = 3 × 17 + 13, then 17 = 1 × 13 + 4, then 13 = 3 × 4 + 1. The gcd is 1, and back-substitution gives 4 × 64 − 15 × 17 = 1. The coefficient of 17 is −15, so the inverse is −15 + 64 = 49. Check: 17 × 49 = 833 = 64 × 13 + 1. ✓
Extended Euclidean Algorithm FAQ
What does the extended Euclidean algorithm do?
It returns three numbers instead of one: the gcd of a and b, and a pair of integers x and y with ax + by = gcd(a, b). The ordinary algorithm gives only the gcd, discarding the information needed to rebuild it.
What are Bézout coefficients?
They are the x and y in ax + by = gcd(a, b). For 252 and 198 the coefficients are 4 and −5, since 4 × 252 − 5 × 198 = 18. Bézout’s identity guarantees such a pair always exists.
Are the Bézout coefficients unique?
No. Infinitely many pairs work. From any solution (x, y), adding b/g to x and subtracting a/g from y gives another. The algorithm returns one particular pair, usually the one with the smallest absolute values.
Which is better, back-substitution or the table?
The table is faster, needs one pass instead of two, and lets you check every row against r = ax + by as you go. Back-substitution is worth doing once, because it shows why the coefficients exist rather than just producing them.
How does this give a modular inverse?
Solve ax + by = 1, which is possible exactly when gcd(a, b) = 1. Reducing that equation modulo a kills the ax term, leaving by ≡ 1 (mod a), so y is the inverse of b modulo a. Add a if the value comes out negative.
Why must the gcd be 1 for an inverse to exist?
Because ax + by can only ever produce multiples of gcd(a, b). If the gcd is 3, no combination reaches 1, so no inverse exists. This is the same condition described in modular inverse.
How fast is the algorithm?
The division count is bounded by roughly 5 times the number of decimal digits in the smaller number. Even 300 digit inputs finish in a few thousand steps, which is why it underpins RSA key generation and the Chinese Remainder Theorem.
What is the connection to ordinary division with remainders?
Every step is a single division producing a quotient and a remainder, of the kind covered in how to find the remainder. The algorithm is a schedule for chaining those divisions and tracking what each one contributes.
