An iterative division-based procedure that computes a greatest common divisor (gcd) of two elements in a Euclidean domain (or any ring with a suitable Euclidean function) by repeated remainder-taking until termination at zero.

Principle

Use the division-with-remainder operation to produce a strictly decreasing sequence of Euclidean norms; termination yields the last nonzero remainder as a gcd, and back-substitution produces Bézout coefficients when applicable.

Demonstration

Integer example: gcd(1071, 462). Compute 1071 = 462·2 + 147, 462 = 147·3 + 21, 147 = 21·7 + 0; the last nonzero remainder is 21, so gcd(1071,462)=21. The extended algorithm gives integers x,y with 1071x+462y=21.

Misapplication

Applying the plain division algorithm in rings without a Euclidean function or assuming the algorithm provides unique gcds in rings lacking appropriate norm properties; also assuming termination without verifying a strictly decreasing measure.

Consequence

Provides an effective method to compute gcds, determine invertibility modulo elements, and produce Bézout representations via the extended algorithm; underpins modular inverses and many algorithmic number-theory procedures.

Reversal

Instead of reducing by remainders, one can synthesize a gcd by factoring both elements into primes and intersecting multisets; this inversion trades iterative reduction for global factor analysis.

Boundary

Valid in Euclidean domains (e.g., Z, F[x]) or in settings equipped with a Euclidean valuation; excludes arbitrary rings without a division algorithm or well-founded norm and requires adjustments (pseudo-division) over general coefficient rings.

Semantic Tension

Sometimes conflated with more general gcd constructions (ideal-theoretic gcds, subresultant algorithms) or with the extended vs. classical variants; tension exists between using the algorithm for exact algebraic gcds and numerical approximations.

Synthesis

The Euclidean algorithm is the procedure of repeated division with remainder driven by a Euclidean valuation; it terminates in a finite number of steps to produce the gcd and, via back-substitution, Bézout coefficients when the domain supports them.