1
The key identity is a one-line proof
Any common divisor of a and b divides a − qb, and conversely. So the two pairs have the same common divisors, hence the same greatest one.
Lesson · Number Theory and Cryptography · The Euclidean algorithm
The Euclidean Algorithm
One identity — gcd(a,b) = gcd(b, a mod b) — repeated. It terminates quickly, provably: consecutive Fibonacci numbers are the worst case and the number of steps is logarithmic.
gcd(a, b) = gcd(b, a mod b) the whole algorithm
gcd(a, 0) = a the base case
worst case: consecutive Fibonacci numbers
steps = O(log min(a,b))
One identity, applied repeatedly
Core ideas
What this lesson establishes
The algorithm is two lines. The interesting parts are why it is correct and why it is fast.
2
It terminates because remainders shrink
Each remainder is strictly smaller than the previous divisor and non-negative, so the sequence must reach 0.
3
It is fast, provably
Two steps at least halve the larger number, so the count is logarithmic. The worst case is consecutive Fibonacci numbers.
The material
The algorithm
The identity, the correctness proof, and the running-time analysis.
Theorem · The key identity
For b > 0, gcd(a, b) = gcd(b, a mod b).
Write a = qb + r with r = a mod b. If d divides a and b, then it divides a − qb = r, so it is a common divisor of b and r.
Conversely if d divides b and r, then it divides qb + r = a, so it is a common divisor of a and b.
The two pairs therefore have exactly the same common divisors, so the greatest is the same.
□
GCD(a, b):
while b ≠ 0:
(a, b) = (b, a mod b)
return a
Correctness is the loop invariant of “Loop Invariants and Program Correctness” in Induction and Recursion: gcd(a, b) never changes, by the identity. Termination holds because b strictly decreases and is a non-negative integer. At exit b = 0 and gcd(a, 0) = a.
How fast
Theorem · Two steps halve
In two iterations, the first argument is at least halved.
If b ≤ a/2 then a mod b < b ≤ a/2 and one step suffices. Otherwise b > a/2, so a = 1·b + (a − b) and a mod b = a − b < a/2.
Either way the value two steps later is below a/2, so the number of iterations is O(log a).
□
Theorem · Lamé's theorem
The number of division steps is at most five times the number of decimal digits of the smaller input, and the worst case occurs exactly for consecutive Fibonacci numbers.
Fibonacci inputs are worst because every quotient is 1 — the slowest possible progress. gcd(F_{n+1}, F_n) takes n − 1 steps, and since F_n grows like φⁿ, that is logarithmic in the input. “Solving Linear Recurrences” in Induction and Recursion supplied the growth rate.
gcd(89, 55): 89 = 1·55 + 34
55 = 1·34 + 21
34 = 1·21 + 13
21 = 1·13 + 8
13 = 1· 8 + 5
8 = 1· 5 + 3
5 = 1· 3 + 2
3 = 1· 2 + 1
2 = 2· 1 + 0 ⟹ gcd = 1
Every quotient is 1 — the slowest the algorithm can ever go.
By contrast gcd(1071, 462) takes three steps despite the numbers being much larger. Size is not what determines the step count; the pattern of quotients is.
In practice
Euclid's algorithm computes gcds of thousand-digit numbers in milliseconds and is used inside every implementation of RSA, in reducing fractions, and in computer algebra generally. It is among the oldest algorithms still in daily use, and it has not been improved on asymptotically for the general case.
Interactive
Number theory workbench
Algorithms with their traces
Method
Running the algorithm
Divide, keep the remainder, repeat.
1
Divide the larger by the smaller
Record the quotient and the remainder. The quotient is not needed for the gcd but is needed for “Bézout's Identity and Modular Inverses”.
2
Replace the pair
(a, b) becomes (b, r). The gcd is unchanged, by the identity.
3
Repeat until the remainder is 0
The remainders strictly decrease, so this happens.
4
Read off the last nonzero remainder
That is the gcd. Equivalently, it is the value of a when b reaches 0.
Euclid
Score 0 / 0Choose the answer you can justify.
gcd(1071, 462)
Three divisions, and a check.
1071 = 2 · 462 + 147
462 = 3 · 147 + 21
147 = 7 · 21 + 0
⟹ gcd(1071, 462) = 21
CHECK 1071 = 21 · 51 462 = 21 · 22
gcd(51, 22) = 1, so 21 is the greatest common divisor.
By factorisation: 1071 = 3 · 7 · 51 = 3² · 7 · 17
462 = 2 · 3 · 7 · 11
common: 3 · 7 = 21 ✓
Three divisions against the eight or so needed to factor both numbers — and the gap widens without limit as the inputs grow. That asymmetry is the practical content of “Greatest Common Divisor”'s warning.
Common mistakes
1
Stopping at the wrong pointThe gcd is the last NONZERO remainder, which is a when b becomes 0. Returning 0 is the classic off-by-one.
2
Requiring a > b to startOne extra step fixes it automatically: if a < b the first division swaps them.
3
Assuming big numbers mean many stepsgcd(1071, 462) takes three steps; gcd(89, 55) takes nine. The quotients decide, not the magnitudes.
Check your understanding
✓
Finish when you can predict the step count.
Run the algorithm on gcd(144, 89) and count the divisions before starting: 144 = F₁₂ and 89 = F₁₁, so the body's rule names the number. Consecutive Fibonacci numbers give the maximum, and knowing that in advance is the analysis working.
Note: “Bézout's Identity and Modular Inverses” runs the same divisions backwards to produce Bézout's coefficients, which is where modular inverses come from — and therefore where RSA's private key comes from. The quotients recorded here are exactly what that needs.