Euclidean Algorithm (GCD)

Math / Number Theory O(log min(a, b)) O(1)

Computes the greatest common divisor by replacing the pair (a, b) with (b, a mod b) until the remainder is zero.

gcd(252,105)

1/12

Find gcd(252, 105).

Invariantgcd(a, b) = gcd(b, a mod b), so every step shrinks the pair without changing the answer.

euclidean-gcd.c

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;    /* a = q*b + r */
        a = b;
        b = r;
    }
    return a;
}

How Euclidean Algorithm (GCD) works

gcd(a, b) = gcd(b, a mod b): any common divisor of a and b also divides the remainder. Remainders shrink fast — at least halving every two steps — so the chain is logarithmic.

When to use it

Reducing fractions, LCM via a·b/gcd, the base of modular arithmetic routines.