Euclidean algorithm

For positive integers a and b with a ≥ b, divide a by b and write a = qb + r, where q is the quotient and 0 ≤ r < b. Replace the pair (a, b) with (b, r) and repeat. For example, to find the greatest common divisor of 252 and 105: 252 = 2 × 105 + 42; 105 = 2 × 42 + 21; 42 = 2 × 21 + 0. The final nonzero remainder, 21, is the greatest common divisor. If the starting numbers are equal, the first remainder is zero and that common value is the answer.

A number divides both a and b exactly when it divides both b and the remainder r = a − qb. The two pairs therefore have the same common divisors and the same greatest common divisor. At each step, the remainder is a nonnegative integer smaller than the previous divisor, so the sequence must terminate. When the remainder reaches zero, the last nonzero remainder divides the preceding terms; because the common divisors have been preserved at every step, it is the greatest common divisor of the original pair.

Working backward through the division equations expresses the greatest common divisor d as an integer linear combination of the inputs: d = xa + yb for some integers x and y. This is known as Bézout's identity. In the example above, 21 = 5 × 105 − 2 × 252. The result helps determine when an equation ax + by = c has integer solutions: such solutions exist exactly when the greatest common divisor of a and b divides c. When that divisor is 1, the coefficients also provide a multiplicative inverse in modular arithmetic. The algorithm is used in number theory and remains practical for computer calculation.

The method is named for Euclid, whose Elements describes finding a greatest common measure of two numbers in Book VII. Proposition 2 presents a repeated-subtraction procedure: subtract the smaller magnitude from the larger until the common measure is exposed. Repeated division with remainders is a more efficient form of the same principle. Britannica dates Euclid's account to about 300 BCE. The modern algorithm retains the ancient idea that replacing a pair by a smaller pair can preserve its common divisors while making progress toward a result.