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.