Key takeaways
- The Euclidean algorithm uses gcd(a, b) = gcd(b, r), where r is the remainder of a divided by b, and repeats until the remainder is 0.
- The last nonzero remainder is the greatest common divisor: gcd(1071, 462) = 21.
- It works because every common divisor of a and b also divides r = a − qb, so the pairs (a, b) and (b, r) share the same divisors.
- It is fast: the number of steps is at most five times the number of digits of the smaller number, with consecutive Fibonacci numbers as the worst case.
- Running the steps backwards, the extended algorithm writes the gcd as ax + by, which is how modular inverses are found.
The greatest common divisor of two integers, gcd(a, b), is the largest integer that divides both. You can find it by factorising both numbers, but for large numbers factorising is slow. Applied Discrete Structures puts it bluntly: as early as Euclid's time it was known that factorisation wasn't the best way to compute greatest common divisors. The better way is the Euclidean algorithm, which MathWorld notes was given, for rational numbers, in Book VII of Euclid's Elements.
The idea in one line
If a = qb + r with 0 ≤ r < b, then
gcd(a, b) = gcd(b, r).
So replace the pair (a, b) by the smaller pair (b, r), and repeat. The numbers shrink every step, and when the remainder becomes 0, gcd(g, 0) = g gives the answer: the last nonzero remainder is the gcd.
Worked example 1: gcd(1071, 462)
| Step | Division | Remainder |
|---|---|---|
| 1 | 1071 = 2 × 462 + 147 | 147 |
| 2 | 462 = 3 × 147 + 21 | 21 |
| 3 | 147 = 7 × 21 + 0 | 0 |
The last nonzero remainder is 21, so gcd(1071, 462) = 21. Check: 1071 = 21 × 51 and 462 = 21 × 22, and 51 and 22 share no factor. As a bonus, 1071/462 simplifies to 51/22: dividing by the gcd is a reliable way to simplify a fraction with large numbers.
Worked example 2: gcd(252, 198)
| Step | Division | Remainder |
|---|---|---|
| 1 | 252 = 1 × 198 + 54 | 54 |
| 2 | 198 = 3 × 54 + 36 | 36 |
| 3 | 54 = 1 × 36 + 18 | 18 |
| 4 | 36 = 2 × 18 + 0 | 0 |
So gcd(252, 198) = 18.
Why it works
Suppose a = qb + r.
- If d divides a and b, then d divides a − qb = r. So every common divisor of a and b is a common divisor of b and r.
- If d divides b and r, then d divides qb + r = a. So every common divisor of b and r is a common divisor of a and b.
The two pairs have exactly the same common divisors, so they have the same greatest one. Each step preserves the gcd while making the numbers smaller, and since remainders are non-negative integers that strictly decrease, the process must stop. That last argument, a decreasing sequence of natural numbers cannot go on forever, is the well-ordering idea behind induction.
How fast is it?
Very fast. MathWorld records Lamé's result that the number of steps is never more than five times the number of decimal digits in the smaller number, and that the worst case occurs for two consecutive Fibonacci numbers. For instance, gcd(89, 55) takes nine divisions (89, 55, 34, 21, 13, 8, 5, 3, 2, 1, each remainder the previous Fibonacci number), against at most 5 × 2 = 10 allowed by the bound.
In the language of big-O notation, the number of steps grows linearly with the number of digits, that is, logarithmically with the size of the numbers. That is why the algorithm stays practical even for numbers with hundreds of digits.
In code
The recursive form is a direct translation of the key identity:
gcd(a, b):
if b == 0: return a
return gcd(b, a mod b)
It does not even need a ≥ b. If a < b, the first call computes a mod b = a and simply swaps the pair.
gcd and lcm
For positive integers, gcd(a, b) × lcm(a, b) = a × b. So the least common multiple comes free: lcm(252, 198) = 252 × 198/18 = 2,772. Under the "divides" ordering, the gcd and lcm are the greatest lower bound and least upper bound of the two numbers, which is how they appear in Hasse diagrams.
The extended Euclidean algorithm
Running the divisions backwards expresses the gcd as a combination of the original numbers. From example 1:
21 = 462 − 3 × 147 and 147 = 1071 − 2 × 462, so
21 = 462 − 3 × (1071 − 2 × 462) = 7 × 462 − 3 × 1071.
That gcd(a, b) can always be written as ax + by for some integers x and y is Bézout's lemma, which Applied Discrete Structures states and proves. A key use is finding modular inverses: if gcd(a, n) = 1, then ax + ny = 1, so ax ≡ 1 (mod n) and x is the inverse of a. Modular inverses with the extended Euclidean algorithm works through the table method.
Three gcds to compute
- Find gcd(391, 299). (Remainders 92, 23, 0: the gcd is 23.)
- Find gcd(144, 89) and count the steps. Why so many?
- Write gcd(252, 198) = 18 as 252x + 198y.
The gcd belongs to the number theory and modular arithmetic unit of Discrete Math: Study & Quiz, which pairs naturally with the rules of modular arithmetic. Levin's open textbook covers the same ground in its introduction to number theory. Browse our education apps, or see the discrete math hub for the full number theory sequence.
Good to know
Frequently asked questions
How does the Euclidean algorithm work?
Why does the Euclidean algorithm give the correct answer?
How many steps does the Euclidean algorithm take?
How do you find the lcm using the gcd?
Sources
- Euclidean Algorithm (opens in a new tab)Wolfram MathWorld — accessed
- Greatest Common Divisors and the Integers Modulo n: The Euclidean Algorithm (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
- Introduction to Number Theory (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.