The Euclidean Algorithm: Computing a Greatest Common Divisor

On this page

Interactive

Replace (a, b) by (b, a mod b) until the remainder is zero

DivideAutoReset

a

252

b

105

Division trace

#	a	b	q	r

Press Divide to run the first division.

a = q·b + r, 0 ≤ r < b · gcd(a, b) = gcd(b, r)

Computing a greatest common divisor by listing all divisors becomes slow as the inputs grow. The Euclidean algorithm replaces a pair by a smaller pair with the same common divisors, until the answer is visible. This article uses the nonnegative convention $\gcd(0,0)=0$.

Why the replacement works

Let $a,b$ be nonnegative integers with $b>0$. Euclidean division gives unique integers $q,r$ with

$a=bq+r,\qquad 0\le r<b.$

Then

$\gcd(a,b)=\gcd(b,r).$

Indeed, any integer dividing both $a,b$ also divides $a-bq=r$, and any integer dividing both $b,r$ also divides $bq+r=a$. Thus the two pairs have exactly the same common divisors, so their greatest nonnegative common divisor is the same.

Trace and termination

For $252$ and $105$, the successive divisions are

$252=2\cdot105+42,\qquad105=2\cdot42+21,\qquad42=2\cdot21+0.$

Each replacement preserves the gcd, so

$\gcd(252,105)=\gcd(105,42)=\gcd(42,21)=\gcd(21,0)=21.$

Whenever the remainder is positive it is smaller than the preceding divisor. The nonnegative remainders therefore decrease strictly and must eventually reach zero. The last nonzero value is the gcd. In particular, $\gcd(a,0)=a$ for every nonnegative $a$, including the conventional value $\gcd(0,0)=0$.

For positive inputs, the number of divisions is $O(\log\min(a,b))$: in the slowest case the remainders follow consecutive Fibonacci-sized values, so the smaller input decreases by a constant factor every two steps. This counts arithmetic steps, not the bit cost of operating on arbitrarily large integers.

Iterative C++ implementation

The function accepts only nonnegative int values representable by int. This precondition avoids relying on C++ remainder behavior for negative inputs; it returns the nonnegative gcd and gives gcd(0, 0) == 0.

int gcd(int a, int b) {
    // Precondition: a >= 0 and b >= 0.
    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

At each pass, remainder is the $r$ in $a=bq+r$, and the pair becomes $(b,r)$ without changing its gcd. When b is zero, a is the result.