➗ GCD & LCM

The Euclidean algorithm is 2,300 years old and still the fastest way to the greatest common divisor: keep dividing, keep the remainder, stop at zero — the last divisor is the gcd. This page prints each division as it runs so you can see why the answer is what it is, then builds the least common multiple from it: lcm(a,b) = a×b ÷ gcd(a,b).

Why Euclid beats brute force

Factoring both numbers to find shared primes is exponential work for anything the size of a cryptographic integer; Euclid needs only about five times the digit count in divisions — computing gcd of two 64-bit numbers is microseconds of arithmetic. That speed is why the algorithm sits inside every rational-arithmetic library, every calendar cycle calculation and, since the 1970s, the RSA key generator: the extended version of these same subtraction steps also finds the modular inverse that makes RSA keys possible.

Part of Everyday Tools. Like everything on tukuk.org: free, no account, no tracking.