How to Find the GCD Using the Euclidean Algorithm

The Euclidean algorithm finds the GCD by repeatedly replacing the larger number with the remainder of dividing it by the smaller, until the remainder is zero. The last non-zero number is the GCD.

It's over 2,000 years old, runs in just a handful of steps even for huge numbers, and underpins modern cryptography. Here's how to use it.

The algorithm in one line

gcd(a, b) = gcd(b, a mod b), repeated until the second number is 0.

Example — gcd(48, 36): gcd(48, 36) → gcd(36, 12) → gcd(12, 0) = 12. Three steps, done.

A bigger example

gcd(1071, 462): 1071 mod 462 = 147 → gcd(462, 147); 462 mod 147 = 21 → gcd(147, 21); 147 mod 21 = 0 → GCD = 21. Even large numbers resolve in a few divisions.

Why it works

Any common divisor of a and b also divides their remainder a mod b. So the set of common divisors never changes as you reduce — and the process must end because remainders shrink. The final divisor is therefore the greatest one shared by the originals.

Where it's used

• Simplifying fractions to lowest terms — see the Fraction Simplifier.
• Modular inverses in RSA cryptography (the extended Euclidean algorithm).
• Computer graphics and tiling problems.