Euclid's GCD trick still secures internet math
Replace the larger integer by its difference with the smaller—or better, by the remainder after division—and the greatest common divisor stays put. Euclid wrote that down around 300 BC; Gabriel Lamé later bounded the steps, and cryptography still leans on the idea.
The Euclidean algorithm computes the greatest common divisor of two integers, the biggest number that divides both with nothing left over. Euclid set it out in his Elements around 300 BC, and it remains one of the oldest algorithms in regular use. The GCD travels under other names too, including greatest common factor, highest common factor, and greatest common measure. Two numbers whose GCD is 1 are called coprime, which does not make either one prime: 6 and 35 are both composite yet share no factor except 1.
Everything rests on one observation: subtracting the smaller number from the larger leaves the GCD unchanged. Because 252 and 105 are 21 × 12 and 21 × 5, their GCD is 21, and 105 and 147 share that same answer. Repeating the swap shrinks the pair until the two numbers match. Euclid's subtraction version can crawl when one number dwarfs the other, so the faster form replaces the larger number with its remainder after division and halts at a remainder of zero. For 1071 and 462 the remainders run 147, 21, 0, giving 21. Gabriel Lamé proved in 1844 that this version never needs more steps than five times the decimal digits of the smaller input, a result often taken as the start of computational complexity theory.
A picture helps: a 24-by-60 rectangle can be tiled with squares of side 1, 2, 3, 4, 6, or 12, and the GCD is the largest of these. Equivalently, the GCD multiplies the prime factors two numbers share, so 1386 and 3213 give 3 × 3 × 7 = 63. It is also the smallest positive value of ua + vb for integers u and v, a view that matters in ring theory. And because gcd(a, b, c) can be found pair by pair, the two-number method handles any number of inputs.
Uses range from reducing fractions and dividing in modular arithmetic to solving Diophantine equations. Its arithmetic sits inside the cryptographic protocols that protect internet traffic, and inside methods for attacking those systems by factoring large composite numbers. In the nineteenth century it was extended to Gaussian integers and to polynomials in one variable, which gave rise to the abstract idea of a Euclidean domain.
Source: Euclidean algorithm
