Euclidean algorithm

The Euclidean algorithm computes the greatest common divisor of two integers by repeated division. For integers a and b with a greater than or equal to b greater than 0, write a = bq + r, where q is the quotient and 0 less than or equal to r less than b. The algorithm then replaces the pair (a,b) with (b,r). It stops when the remainder is zero; the preceding nonzero remainder is gcd(a,b).¹

For example, gcd(252,105) is found through 252 = 105 times 2 + 42, 105 = 42 times 2 + 21, and 42 = 21 times 2 + 0. The answer is therefore 21. The method works because any common divisor of a and b also divides a minus bq, which is the remainder r. Thus the pairs (a,b) and (b,r) have exactly the same common divisors, while the numbers decrease until termination.

A compact version is: while b is not zero, replace (a,b) by (b, a modulo b); return a. Signs can be handled by taking absolute values, and gcd(a,0) is conventionally the absolute value of a.

The algorithm is correct because the common divisors remain unchanged at every step. If a = bq + r, then a divisor d divides both a and b exactly when it divides both b and r: from a = bq + r, divisibility in one direction is immediate, and r = a - bq gives the reverse direction.²

Termination follows from a simpler fact: each positive remainder is strictly smaller than the divisor that preceded it. The sequence of remainders therefore descends through positive integers and must eventually reach zero. The last nonzero remainder is a common divisor of the original inputs, and the invariant above shows that every common divisor of those inputs divides it. It is consequently the greatest common divisor.

The same reasoning explains why the algorithm is preferable to testing every possible divisor. Its number of division steps grows logarithmically with the smaller input in the worst case, rather than linearly with the value of that input. The consecutive Fibonacci numbers provide a classic slow case: their neighboring quotients are mostly 1, so they require unusually many steps relative to their size.³

The extended Euclidean algorithm records additional information: integers x and y such that ax + by = gcd(a,b). This identity is called Bézout's identity, and the coefficients can be recovered by substituting backward through the divisions or by maintaining coefficient pairs during the computation.²

These coefficients make the method useful beyond finding a divisor. If gcd(a,m) = 1, the coefficient of a in a Bézout identity gives a multiplicative inverse of a modulo m. Modular inverses are central to solving linear congruences, reducing fractions in modular arithmetic, and constructing algorithms in computational number theory.

Public-key cryptography uses the same idea in several places. In RSA, the private exponent is chosen as an inverse modulo a value derived from the prime factors of the modulus; the extended algorithm supplies that inverse when the relevant numbers are coprime.⁴ The algorithm also supports rational-number normalization, polynomial gcd computations, and symbolic algebra, although polynomial versions replace integer division with division in a polynomial coefficient system.

The method is one of the oldest continuously used algorithms in mathematics. Euclid described a geometric form in the Elements, presenting repeated subtraction of magnitudes rather than the modern remainder notation; the division-based formulation is a faster restatement of the same invariant.⁵

Repeated subtraction is easy to understand but can be inefficient when the inputs differ greatly. For instance, subtracting 1 from a number many times may require thousands of operations, whereas division eliminates many possibilities in one step. Modern descriptions therefore use quotient and remainder, while preserving Euclid's central idea that the common divisors do not change.

Several practical variants reduce the cost of arithmetic on machine words or very large integers. The binary gcd algorithm replaces division by comparisons, subtraction, and powers of two, which can be advantageous on hardware where bit operations are inexpensive. For enormous integers, accelerated methods such as the half-gcd algorithm organize several Euclidean steps together and are used in computer algebra libraries.³

The Euclidean algorithm is also a source of information about the continued-fraction structure of a rational number. The successive quotients produced while computing gcd(a,b) are exactly the partial quotients in the continued fraction of a divided by b. This connection links divisibility, rational approximation, and the theory of continued fractions.²

Its worst-case behavior is tied to Fibonacci numbers, but average behavior is substantially better than that extreme case. The quotients are not merely bookkeeping: they describe how efficiently one integer can be approximated by ratios formed from the other. The algorithm therefore appears in approximation theory as well as elementary divisibility.

There are useful edge cases. If both inputs are zero, every integer divides them, so no greatest positive common divisor exists; software libraries typically reject or separately define this case. If one input is zero, the other input, after taking its absolute value, is returned. The gcd is also unchanged when either input is replaced by its sum with an integer multiple of the other, a form particularly useful in lattice calculations and integer matrix reduction.

Greatest common divisor

The largest positive integer that divides two or more integers without a remainder.

Remainder

The value left after dividing one integer by another; in the algorithm it is strictly smaller than the positive divisor.

Bézout's identity

The equation ax + by = gcd(a,b) for some integers x and y.

Extended Euclidean algorithm

A version of the algorithm that computes both a greatest common divisor and Bézout coefficients.

Continued fraction

An expression built from repeated integer quotients; the Euclidean algorithm supplies the quotients for a ratio of integers.