Euclidean algorithm

Factoring a large number is hard, but dividing is easy. The Euclidean algorithm uses the fact that \(\gcd(a,b)=\gcd(b,r)\) when \(a=qb+r\): the common divisors of \(a\) and \(b\) are exactly those of \(b\) and \(r\). Repeat until the remainder is 0; the last nonzero remainder is the answer. For \(a=252\) and \(b=105\): \(252=2\cdot105+42\), \(105=2\cdot42+21\), \(42=2\cdot21+0\), so \(\gcd(252,105)=21\).

It always terminates because the remainders are nonnegative integers that strictly decrease. It is also very fast: every two steps the remainder at least halves, so the number of divisions is proportional to the number of digits. The worst case is two consecutive Fibonacci numbers: \(\gcd(89,55)\) needs 9 divisions, all with quotient 1. If \(a<b\), the first step simply swaps the numbers.

Working backwards through the divisions gives the extended version: integers \(x,y\) with \(ax+by=\gcd(a,b)\), Bézout's identity. It solves Diophantine equations \(ax+by=c\) and computes inverses modulo \(m\), the basis of RSA cryptography. A common mistake is to stop at the remainder 0 instead of taking the previous one: the answer is the last nonzero remainder, that is, the last divisor.