Euclidean algorithm

Finding the greatest common divisor by factoring both numbers can be slow for large values. The Euclidean algorithm sidesteps factoring entirely with a clever trick: it keeps replacing the bigger number by the remainder it leaves when divided by the smaller, watching the numbers shrink until one becomes zero.

The procedure works like this. To find gcd(a, b) with a greater than b, divide a by b and keep the remainder r. Then forget a and find gcd(b, r) the same way. Repeat. Each step the remainder gets strictly smaller, so eventually a remainder hits 0 — and the last nonzero remainder is the gcd. The idea relies on the fact that gcd(a, b) equals gcd(b, a mod b).

This algorithm is over two thousand years old and still one of the fastest known. It is also the engine behind the extended Euclidean algorithm, which not only finds the gcd but expresses it as an integer combination of a and b — the content of Bezout's identity, and a key step in solving linear Diophantine equations and computing modular inverses.