The Euclidean Algorithm Explained (Find the GCD Step by Step)

Why gcd(a, b) = gcd(b, a mod b)

Write a = qb + r, where r = a mod b. Any number that divides both a and b also divides a − qb, which is r. So every common divisor of a and b is a common divisor of b and r. The argument also runs backwards: a common divisor of b and r divides qb + r = a. The two pairs therefore have exactly the same common divisors, and so the same greatest one.

Each step makes the remainder strictly smaller than the divisor, so the process must reach 0 after finitely many steps. At that point gcd(x, 0) = x.

The steps

1. Divide the larger number by the smaller and write a = q·b + r.
2. If r = 0, stop: the GCD is b.
3. Otherwise replace (a, b) with (b, r) and repeat.
4. The GCD is the last non-zero remainder, which is the divisor in the final line.

Example 1: gcd(252, 105)

The remainder reaches 0 on step 3, and the divisor on that line is 21, so gcd(252, 105) = 21.

The least common multiple follows from gcd(a, b) × lcm(a, b) = |a × b|. Here lcm(252, 105) = 252 × 105 ÷ 21 = 1260.

Example 2: the slowest case, gcd(89, 55)

Consecutive Fibonacci numbers are the worst case, because every quotient is 1 and the remainder shrinks as slowly as it can.

Nine divisions give gcd(89, 55) = 1, so the numbers are coprime. Lamé's theorem (1844) states that the number of division steps never exceeds five times the number of decimal digits of the smaller number, so the method needs only about log n steps.

The extended Euclidean algorithm

Bézout's identity says that for any integers a and b there are integers x and y with ax + by = gcd(a, b). The extended algorithm finds them by working backwards through the division steps.

Take a = 240 and b = 46. Forward:

1. 240 = 5 × 46 + 10
2. 46 = 4 × 10 + 6
3. 10 = 1 × 6 + 4
4. 6 = 1 × 4 + 2
5. 4 = 2 × 2 + 0, so gcd = 2

Now solve each line for its remainder and substitute upward:

1. 2 = 6 − 1 × 4
2. 4 = 10 − 1 × 6, so 2 = 6 − (10 − 6) = 2 × 6 − 10
3. 6 = 46 − 4 × 10, so 2 = 2 × (46 − 4 × 10) − 10 = 2 × 46 − 9 × 10
4. 10 = 240 − 5 × 46, so 2 = 2 × 46 − 9 × (240 − 5 × 46) = 47 × 46 − 9 × 240

So 240 × (−9) + 46 × 47 = 2. When gcd(a, m) = 1 this gives a modular inverse: since 3 × 4 = 12 ≡ 1 (mod 11), the inverse of 3 modulo 11 is 4.

Common mistakes

• Giving the final remainder (0) as the answer. The GCD is the last non-zero remainder.
• Dividing the smaller number by the larger on the first step. It works, but wastes a line because the quotient is 0.
• Forgetting the special cases: gcd(0, n) = n, and gcd(0, 0) is usually left undefined or taken as 0.
• Mishandling negatives. gcd(−48, 18) = 6 because the GCD is always non-negative; run the algorithm on absolute values.
• Factoring both numbers when they are large. Factoring is far slower than Euclid's method for big inputs.

Frequently asked questions

Is the Euclidean algorithm the same as finding the HCF?

Yes. HCF (highest common factor) and GCD (greatest common divisor) are two names for the same number.

How do I find the LCM from the GCD?

Use lcm(a, b) = |a × b| ÷ gcd(a, b). Divide first to keep the intermediate numbers small.

What if the GCD is 1?

Then the numbers are coprime (relatively prime). In modular arithmetic this means a has an inverse modulo b.