An iterative division procedure that computes the greatest common divisor (gcd) of two integers by repeatedly replacing the larger number with its remainder upon division by the smaller until the remainder is zero.

Principle

gcd(a,b) = gcd(b, a mod b); repeated application of this reduction decreases the size of operands and terminates with the gcd when a remainder becomes zero.

Demonstration

Compute gcd(48, 18): 48 = 2·18 + 12, 18 = 1·12 + 6, 12 = 2·6 + 0, so gcd(48,18) = 6. The extended algorithm yields coefficients x,y with 48x + 18y = 6.

Misapplication

Applying the algorithm to non-integers without a Euclidean division structure or assuming constant-time performance regardless of operand size are common misuses; another is neglecting to handle negative or zero inputs correctly.

Consequence

The Euclidean algorithm provides an efficient method for gcd computation, underlies modular inverse calculation and Bezout coefficient determination via the extended algorithm, and generalizes to Euclidean domains.

Reversal

Using prime factorization to compute gcd is the conceptual inverse approach; factorization yields gcd but is often far less efficient for large integers than the Euclidean reduction process.

Boundary

Applies to integers and to any Euclidean domain where a division algorithm with remainder exists; it does not directly apply to arbitrary rings lacking a Euclidean norm or to objects without a well-defined remainder operation.

Semantic Tension

Contrast the Euclidean algorithm with binary gcd algorithms and with factorization-based methods: Euclid minimizes remainders via division, whereas binary algorithms exploit binary arithmetic and factorization relies on prime decomposition.

Synthesis

The Euclidean algorithm systematically reduces a gcd problem by remainder division until termination, offering an efficient, generalizable procedure that also yields linear combinations expressing the gcd.