An iterative division-based procedure that computes the greatest common divisor (gcd) of two integers by repeatedly replacing the larger number by its remainder on division by the smaller until the remainder is zero; the last nonzero remainder is the gcd.

Principle

If a and b are integers with a = bq + r, then gcd(a,b) = gcd(b,r). Repeating this step reduces the magnitude of operands, guaranteeing termination, and the extended form back-substitutes remainders to produce Bézout coefficients expressing the gcd as an integer linear combination.

Demonstration

Compute gcd(252, 198): 252 = 198·1 + 54, 198 = 54·3 + 36, 54 = 36·1 + 18, 36 = 18·2 + 0, so gcd = 18. The extended Euclidean algorithm tracks combinations to find x,y with 252x + 198y = 18.

Misapplication

Using floating-point division without exact remainder control for integer gcds or failing to normalize signs and zeros; assuming naive Euclidean steps fully capture complexity costs for very large integers without considering integer arithmetic models or subquadratic multiplication algorithms.

Consequence

Provides an efficient, provably terminating method to compute gcds, underpins algorithms for modular inverses, simplifying rational numbers, computing orders in cryptography and number theory, and is a building block for polynomial gcds in Euclidean domains.

Reversal

Contrast with subtraction-based gcd algorithms (repeated subtraction) or binary gcd (Stein's algorithm): these accomplish the same gcd computation by different elementary operations and may be preferable in certain hardware or bit-complexity models.

Boundary

Applies in Euclidean domains where a division algorithm with remainder exists (integers, univariate polynomials over a field); it does not directly apply in arbitrary rings lacking a Euclidean function, and input must avoid the trivial both-zero case.

Semantic Tension

Tension between the classical stepwise Euclidean algorithm and modern fast implementations: algorithmically identical in principle but differing in complexity when using fast integer arithmetic or subresultant/polynomial variants for multivariate contexts.

Synthesis

The Euclidean algorithm is the fundamental iterative division process in Euclidean domains that reduces gcd computation to smaller remainders, guarantees termination, yields Bézout representations in its extended form, and underlies many basic constructions in computational number theory and algebra.