Euclidean algorithm

How it works

The algorithm depends on the identity gcd(a, b) = gcd(b, a mod b). Starting with two positive integers a and b (a ≥ b), perform repeated integer division to obtain remainders until one remainder becomes zero. The final nonzero remainder is the greatest common divisor.

1. Divide a by b to get quotient q and remainder r: a = bq + r.
2. If r = 0, then gcd(a, b) = b and stop.
3. Replace (a, b) with (b, r) and repeat from step 1.

Example: gcd(48, 18). Compute 48 = 18·2 + 12, then 18 = 12·1 + 6, then 12 = 6·2 + 0. The GCD is 6.

Variants, properties and complexity

There are several forms of the same idea. A subtraction-based version repeatedly replaces the larger number by its difference with the smaller; the binary GCD (Stein's) uses only shifts and subtraction. The algorithm is efficient: the number of division steps grows roughly with the number of digits of the inputs, so it is fast even for large integers used in modern computation.

Extended algorithm and applications

The extended Euclidean algorithm produces integers x and y satisfying ax + by = gcd(a, b). This extra output is essential for solving linear Diophantine equations, computing modular inverses, and many cryptographic routines (for example in public-key systems). Repeated application gives the GCD of more than two numbers.

History and significance

The procedure traces back to ancient mathematics and appears in Euclid's Elements as an argument rather than modern code. Its longevity reflects its fundamental role: it underpins simplification of fractions, computation in algebraic structures, and efficient integer arithmetic in algorithms and number-theoretic applications.