Every time your browser opens a secure connection, it works with greatest common divisors of enormous numbers — hundreds of digits long. Hunting for their divisors one by one would take longer than the age of the universe, so we need something far cleverer.

Listing divisors or factorising is slow. Around 300 BC, Euclid found a method for the greatest common divisor that is breathtakingly fast and needs no factorising at all. It is the oldest algorithm still in everyday use — and it rests entirely on one short observation about remainders.

The key fact

If a = bq + r, then any number that divides both a and b also divides r (since r = a - bq), and vice versa. So the pair (a, b) and the pair (b, r) share exactly the same common divisors — and therefore the same gcd:

Each step replaces a pair with a smaller pair without changing the answer. Keep going and the second number shrinks to 0 — at which point the first number is the gcd, because \gcd(g, 0) = g.

A worked example: \gcd(48, 18)

Replace the larger number by the remainder, over and over:

The last non-zero remainder is 6, so \gcd(48, 18) = 6. Three short divisions — no factorising in sight. Even for thousand-digit numbers this finishes almost instantly.

See it as squares

There is a gorgeous geometric picture. Tile a w \times h rectangle with the largest squares that fit: each division \,\text{(big)} = \text{(small)}\cdot q + r\, lays down q squares and leaves a smaller rectangle to tile next. The side of the final square is the gcd — the largest square that tiles the whole rectangle exactly. Step through it; press refresh for a new pair.

See it explained