Finding GCD Using the Euclidean Algorithm

What is the GCD?

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both of them evenly. For example, GCD(12, 8) = 4 because 4 is the largest number that divides both 12 and 8.

Other names: greatest common factor (GCF), highest common factor (HCF).

The Euclidean Algorithm

The Euclidean algorithm finds the GCD efficiently by repeated division. The key insight: GCD(a, b) = GCD(b, a mod b). Keep replacing the larger number with the remainder until the remainder is 0. The last non-zero remainder is the GCD.

Step-by-step: Find GCD(252, 198)

Step 1: Divide 252 by 198.

$252 = 198 \times 1 + 54$

Remainder = 54. So GCD(252, 198) = GCD(198, 54).

Step 2: Divide 198 by 54.

$198 = 54 \times 3 + 36$

Remainder = 36. So GCD(198, 54) = GCD(54, 36).

Step 3: Divide 54 by 36.

$54 = 36 \times 1 + 18$

Remainder = 18. So GCD(54, 36) = GCD(36, 18).

Step 4: Divide 36 by 18.

$36 = 18 \times 2 + 0$

Remainder = 0. Stop! The last non-zero remainder is 18.

$\boxed{\text{GCD}(252, 198) = 18}$

Verification: $252 / 18 = 14$ ✓ and $198 / 18 = 11$ ✓. Both divide evenly, and 14 and 11 share no common factors, confirming 18 is the greatest.

Why the algorithm works

If $a = bq + r$, then any number that divides both $a$ and $b$ must also divide $r$ (since $r = a - bq$). And any number dividing both $b$ and $r$ must also divide $a$ (since $a = bq + r$). So the set of common divisors doesn't change when we replace $(a, b)$ with $(b, r)$.

Efficiency

The Euclidean algorithm is remarkably fast — it takes at most $2 \log_2(\min(a, b))$ steps. Even for numbers with hundreds of digits, it terminates quickly. This is why it's used in cryptography (RSA key generation).

Alternative: listing factors (slow method)

Factors of 252: 1, 2, 3, 4, 6, 7, 9, 12, 14, 18, 21, 28, 36, 42, 63, 84, 126, 252. Factors of 198: 1, 2, 3, 6, 9, 11, 18, 22, 33, 66, 99, 198. Common factors: 1, 2, 3, 6, 9, 18. Greatest = 18 ✓.

This method works but is impractical for large numbers. The Euclidean algorithm is far superior.

Common mistakes

• Dividing the wrong way. Always divide the larger number by the smaller (or equivalently, the current pair is always (bigger, smaller)).
• Stopping too early. Keep going until the remainder is exactly 0. The GCD is the last non-zero remainder, not the first remainder.
• Confusing GCD with LCM. GCD is the largest common divisor; LCM is the smallest common multiple. They're related: $\text{GCD}(a,b) \times \text{LCM}(a,b) = a \times b$.

Try it in the visualization

Enter two numbers. Each step of the Euclidean algorithm is animated — the division, the remainder, and the replacement. The chain of equations leads to the GCD. Toggle "show factor method" to compare with the brute-force approach.