Euclidean algorithm

Euclid’s algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers.

Starting with \(k=0\), each step uses two non-negative remainders \(r_{k-2}\) and \(r_{k-1}\) where \(r_{k-2} > r_{k-1}\). The \(k\)th step then provides the quotient \(q_k\) and remaining \(r_k\) where \[ r_{k-2} = q_{k}r_{k-1} + r_{k} \] At the initial step remainders are set to the two inputs so that \(r_{-2}= a\) and \(r_{-1}= b\) allowing the following expansion \[ \begin{align*} a &= q_{0b} + r_0\\ b &= q_{1}r_{0} + r_1\\ r_{0} &= q_{2}r_{1} + r_2\\ r_{1} &= q_{3}r_{2} + r_{3}\\ &\vdots \end{align*} \]

Iterative implementation

GCD(a, b):
    WHILE b ≠ 0
        t ← b
        b ← a mod b
        a ← t
    RETURN a

Recursive implementation

GCD(a, b):
    IF b = 0
        RETURN a
    ELSE
        RETURN GCD(b, a mod b)