Euclidean Algorithm

Also Known As

TL;DR

Explanation

The Euclidean algorithm finds the greatest common divisor (GCD) of two non-negative integers based on the principle that gcd(a, b) equals gcd(b, a mod b). You repeatedly replace the pair (a, b) with (b, a mod b) until the second value reaches zero; the remaining non-zero value is the GCD. It runs in O(log min(a, b)) time because each step reduces the operands by at least a constant factor (the Fibonacci numbers are the worst case). The algorithm can be written recursively or iteratively, and the iterative form avoids any stack-depth concerns for large inputs.

The original subtraction-based form repeatedly subtracts the smaller value from the larger, but this degrades to O(a) when one operand is much larger - the modulo form fixes that by collapsing many subtractions into a single division. The extended Euclidean algorithm additionally computes integer coefficients x and y such that a*x + b*y = gcd(a, b), which is the foundation of modular inverses used in RSA and other cryptographic schemes.

Practical uses include reducing fractions to lowest terms, computing the least common multiple via lcm(a, b) = a / gcd(a, b) * b, checking coprimality, and clock or modular arithmetic. Because it relies only on integer remainders, it works for arbitrarily large integers as long as your language supports big integers; PHP's intdiv and modulo operators handle 64-bit values, and the GMP extension handles bignums.

Common pitfalls involve negative inputs (take absolute values first), the zero edge case (gcd(0, 0) is conventionally 0, and gcd(n, 0) is n), and integer overflow when computing the LCM by multiplying before dividing. Keeping the operands ordered is unnecessary because the first modulo step automatically swaps them.

Diagram

flowchart TD
    START[gcd a=48 b=18] --> S1[48 mod 18 = 12<br/>now gcd 18,12]
    S1 --> S2[18 mod 12 = 6<br/>now gcd 12,6]
    S2 --> S3[12 mod 6 = 0<br/>now gcd 6,0]
    S3 --> DONE[b is 0<br/>GCD = 6]
style DONE fill:#238636,color:#fff
style START fill:#1f6feb,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Using repeated subtraction instead of modulo, which becomes O(a) for very unequal operands.
• Forgetting to take absolute values, producing wrong results for negative inputs.
• Computing LCM as a * b / gcd, which overflows before dividing instead of a / gcd * b.
• Mishandling the zero case where gcd(n, 0) should return n.
• Writing deep recursion for huge inputs when an iterative loop avoids stack growth.

Avoid When

• You need the GCD of polynomials or non-integer values, where a specialised algorithm applies.
• Inputs exceed 64-bit range and you are not using a bignum library like GMP, risking overflow.
• A language built-in such as gmp_gcd or math.gcd already provides a tested, optimised implementation.

When To Use

• Reducing fractions to lowest terms by dividing numerator and denominator by their GCD.
• Computing LCM, checking coprimality, or working with modular arithmetic.
• Deriving modular inverses via the extended Euclidean algorithm for cryptographic math.
• Any time you need an exact integer ratio between two quantities quickly.

Code Examples

// Subtraction form - O(a) when operands are very unequal:
function gcd(int $a, int $b): int {
    while ($a !== $b) {
        if ($a > $b) {
            $a -= $b;   // gcd(1000000, 1) loops ~1,000,000 times
        } else {
            $b -= $a;
        }
    }
    return $a; // also breaks if either input is 0
}

// Modulo form - O(log min(a,b)), handles negatives and zero:
function gcd(int $a, int $b): int {
    $a = abs($a);
    $b = abs($b);
    while ($b !== 0) {
        [$a, $b] = [$b, $a % $b]; // first step swaps automatically
    }
    return $a; // gcd(n, 0) returns n
}

function lcm(int $a, int $b): int {
    if ($a === 0 || $b === 0) return 0;
    return intdiv(abs($a), gcd($a, $b)) * abs($b); // divide before multiply
}

Tags

Related Terms

References

• https://en.wikipedia.org/wiki/Euclidean_algorithm
• https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm