Euclidean Algorithm

The Euclidean algorithm is an algorithm for computing the greatest common divisor (GCD) of two integers: the largest positive integer dividing both, provided they are not both zero. It repeatedly performs division with remainder until a remainder becomes zero; the last nonzero remainder is the answer. The method is fundamental in number theory and extends to polynomials and other algebraic structures. It computes the GCD without requiring the prime factorizations of its inputs. (cs.drexel.edu)

Historical formulation

The algorithm is named after Euclid, whose Elements presents the procedure in Book VII. Proposition 1 concerns recognizing relatively prime numbers, while Proposition 2 finds the greatest common measure of two numbers that are not relatively prime. Proposition 3 extends the construction to three numbers. The ancient formulation uses repeated subtraction rather than modern division notation: the smaller quantity is repeatedly removed from the larger. Division with remainder groups multiple such subtractions into one operation. (mathcs.clarku.edu)

Procedure and example

For positive integers $a\geq b$, Euclidean division gives uniquely determined integers $q$ and $r$ satisfying

The algorithm replaces $(a,b)$ with $(b,r)$ and repeats. When the second component becomes zero, the first component is the GCD. This rule can be implemented iteratively or through recursion. (cs.drexel.edu)

For example, applying the rule to 252 and 105 gives

Thus $\gcd(252,105)=21$. The quotients are 2, 2, and 2; the last nonzero remainder is 21.

A compact pseudocode formulation, for nonnegative inputs not both zero, is:

gcd(a, b):
    while b ≠ 0:
        r ← a mod b
        a ← b
        b ← r
    return a

Here mod denotes the nonnegative remainder. The temporary variable preserves the old values during each update. The loop also handles $a<b$: its first iteration exchanges the roles of the inputs. (mosullivan.sdsu.edu)

Correctness and termination

The central identity is

Its proof follows from divisibility. Every common divisor of $a$ and $b$ divides $a-qb$. Conversely, every common divisor of $b$ and $a-qb$ divides their sum $(a-qb)+qb=a$. Consequently, the two pairs have exactly the same common divisors. (mosullivan.sdsu.edu)

The unchanged GCD is a loop invariant. Meanwhile, successive nonzero remainders form a strictly decreasing sequence of positive integers, so the process must terminate. At termination, the pair is $(d,0)$, whose greatest common divisor is $d$. These two properties establish that the returned value is correct. (mosullivan.sdsu.edu)

Extended algorithm and applications

The extended Euclidean algorithm additionally computes integers $x$ and $y$ satisfying Bézout's identity:

Each remainder is an integer linear combination of the original inputs. Tracking its coefficients during division, or substituting backward through the equations afterward, produces the required coefficients. (cs.drexel.edu)

For the example above,

Thus $x=-2$ and $y=5$.

This extension solves linear Diophantine equations. For $a,b$ not both zero, the equation $ax+by=c$ has integer solutions exactly when $\gcd(a,b)$ divides $c$. Multiplying Bézout coefficients by $c/\gcd(a,b)$ supplies one solution whenever that condition holds. (web.cs.miami.edu)

In modular arithmetic, if $\gcd(a,m)=1$, then $ax+my=1$ implies $ax\equiv1\pmod m$. Therefore, $x$ represents the modular multiplicative inverse of $a$. Such an inverse exists precisely when $a$ and $m$ are relatively prime. (mosullivan.sdsu.edu)

Efficiency and continued fractions

The algorithm's computational complexity depends on whether one counts divisions or individual bit operations. For positive inputs, the number of divisions is $O(\log\min(a,b))$, expressed using big-O notation. Consecutive Fibonacci numbers produce particularly long remainder chains relative to their size: successive divisions largely follow the Fibonacci recurrence backward. Inputs of at most $n$ bits therefore require $O(n)$ divisions. (sites.math.rutgers.edu)

This does not mean that the running time is linear in the bit length. Division of large integers is itself a multi-operation computation. A straightforward analysis assigning $O(n^2)$ time to each division yields an $O(n^3)$ upper bound, although this bound is not tight; more advanced GCD methods achieve substantially better bit complexity. (sites.math.rutgers.edu)

The successive quotients also give the finite continued fraction expansion of the rational number $a/b$. For the example,

Thus the same division sequence encodes both a common divisor and a continued-fraction representation. (sites.math.rutgers.edu)

Algebraic generalization

For polynomials over a field, division has the form

Replacing $(f,g)$ with $(g,r)$ preserves common divisors, while decreasing degree ensures termination. The last nonzero remainder is a polynomial GCD, determined up to multiplication by a nonzero constant; it is commonly normalized to have leading coefficient 1. (singacom.uva.es)

In abstract algebra, a Euclidean domain is an integral domain admitting division with a remainder whose nonnegative integer-valued size decreases. This supplies the termination mechanism needed for the generalized algorithm. Polynomial rings over fields are examples, with degree serving as the size measure. (singacom.uva.es)