GCD & Euclidean Algorithm

How Euclid's algorithm works

Given two non-negative integers a and b (with a ≥ b), the recursive formula:

gcd(a, b) = gcd(b, a mod b)
gcd(a, 0) = a

Each step replaces the pair (a, b) with (b, a mod b). The remainders shrink rapidly. When the second argument hits 0, the first argument is the GCD.

Worked example — gcd(252, 198)

gcd(252, 198) → 252 mod 198 = 54  → gcd(198, 54)
gcd(198, 54)  → 198 mod 54 = 36  → gcd(54, 36)
gcd(54, 36)   → 54 mod 36 = 18   → gcd(36, 18)
gcd(36, 18)   → 36 mod 18 = 0    → gcd(18, 0)
gcd(18, 0)    → 18

GCD(252, 198) = 18

Five steps from 252 down to 18. The "shrinking" happens fast — each remainder is at most half the previous (in fact, often much smaller). This is why the algorithm is O(log).

Why it's O(log)

Each step of Euclid's algorithm replaces (a, b) with (b, a mod b). It's not obvious that this always halves quickly, but consider:

• If b ≤ a/2, then a mod b ≤ b ≤ a/2 — the larger number halves.
• If b > a/2, then a mod b = a − b < a/2 — the larger number again halves.

So in two consecutive steps, the larger number is at most half what it was — that's why the total number of steps is O(log a). Specifically, no more than 5 × (number of digits in a). The algorithm is among the most efficient in number theory.

Extended Euclidean Algorithm

Bezout's identity says that for any integers a and b:

gcd(a, b) = a·x + b·y

for some integers x and y. The Extended Euclidean Algorithm finds these x and y alongside the GCD. Pseudocode:

extendedGCD(a, b):
    if b == 0: return (a, 1, 0)
    (g, x', y') = extendedGCD(b, a mod b)
    return (g, y', x' - (a / b) * y')

The returned (g, x, y) satisfies a·x + b·y = g. Used to find modular inverses — to compute a⁻¹ mod m, compute extendedGCD(a, m); if gcd is 1, then x is the inverse.

JavaScript — recursive and iterative

// Recursive
function gcd(a, b) {
  return b === 0 ? Math.abs(a) : gcd(b, a % b);
}

// Iterative — slightly faster, no stack growth
function gcdIter(a, b) {
  a = Math.abs(a); b = Math.abs(b);
  while (b) [a, b] = [b, a % b];
  return a;
}

// Extended Euclidean — returns { g, x, y } with ax + by = g
function gcdExtended(a, b) {
  if (b === 0) return { g: a, x: 1, y: 0 };
  const { g, x: x1, y: y1 } = gcdExtended(b, a % b);
  return { g, x: y1, y: x1 - Math.floor(a / b) * y1 };
}

// LCM via GCD
function lcm(a, b) {
  return Math.abs(a * b) / gcd(a, b);
}

// Modular inverse — find x such that ax ≡ 1 mod m
function modInverse(a, m) {
  const { g, x } = gcdExtended(a, m);
  if (g !== 1) return null;  // inverse doesn't exist
  return ((x % m) + m) % m;
}

console.log(gcd(252, 198));        // 18
console.log(gcdExtended(35, 8));   // { g: 1, x: 3, y: -13 } since 35·3 + 8·(-13) = 1
console.log(modInverse(7, 26));    // 15 — since 7·15 = 105 = 4·26 + 1

Applications

• Fraction simplification. Reduce a/b to lowest terms — divide both by gcd(a, b). 252/198 = 18·14/18·11 = 14/11.
• LCM via GCD. lcm(a, b) = a·b/gcd(a, b). For finding common denominators of fractions efficiently.
• RSA modular inverse. Computing the private key d from public key e — extended Euclidean finds d such that ed ≡ 1 mod φ(n).
• Diophantine equations. Solve ax + by = c for integer x, y. Has solutions iff gcd(a, b) divides c. Bezout coefficients give specific solutions.
• Chinese Remainder Theorem. Solve simultaneous congruences using extended Euclidean to find inverses.
• Polynomial GCDs. Same algorithm with polynomial long division. Used in computer algebra systems, simplifying rational functions, finding common roots.

Common mistakes

• Iterating instead of using the modulus. Slow alternative — gcd(a, b) by repeatedly subtracting b from a. Works but takes O(a/b) steps. Use a mod b to take many subtractions in one step — that's the efficient version.
• Forgetting absolute value. gcd(a, b) is conventionally positive. For negative inputs, take absolute values first.
• gcd(0, 0) ambiguity. Some texts define gcd(0, 0) = 0 (largest divisor of nothing is meaningless); others undefined. Algorithms typically return 0 — most contexts where this comes up are degenerate.
• Stack overflow on deeply recursive inputs. Recursive gcd on Fibonacci-style inputs uses log steps but each adds a stack frame. For very large inputs, use the iterative version.
• Wrong order in extended Euclidean. The recursive call returns (x', y') for the smaller pair; the formula for the original pair is (y', x' − (a/b)·y'). Easy to mix up; check by verifying ax + by = g.
• Computing LCM by full factorization. Slow for large numbers. lcm(a, b) = a·b/gcd(a, b) avoids factoring entirely.