Euclid's Algorithm 📐

What is the GCD?

The greatest common divisor (GCD) of two numbers is the largest whole number that divides both of them without leaving a remainder.

For example, the divisors of 12 are 1, 2, 3, 4, 6, 12, and the divisors of 18 are 1, 2, 3, 6, 9, 18. The greatest one they share is 6, so gcd(12, 18) = 6.

We use the GCD when we simplify fractions, share things equally, and even in the cryptography that keeps internet banking safe!

The algorithm

About 2300 years ago, the Greek mathematician Euclid found a fast way to compute the GCD without listing all divisors. The key observation is:

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

where a mod b is the remainder left over after dividing a by b.

• Step 1 — Divide a by b and keep the remainder r: a = q × b + r
• Step 2 — Replace the pair (a, b) with (b, r).
• Step 3 — Repeat until the remainder is 0.
• Done — The last non-zero divisor is the GCD.

Here is the algorithm written in JavaScript — it is the same code used to build every exercise on this page:

// Returns the GCD of a and b, plus every division step.
function euclidSteps(a, b) {
  let x = Math.abs(a);
  let y = Math.abs(b);
  if (x < y) [x, y] = [y, x];   // x must be the larger one
  const steps = [];
  while (y > 0) {
    const q = Math.floor(x / y);  // how many times y fits into x
    const r = x % y;              // the remainder (x mod y)
    steps.push({ x, y, q, r });
    x = y;                          // move b into a's place
    y = r;                          // move the remainder into b's place
  }
  return { gcd: x, steps };      // x is the last non-zero divisor
}

Worked example: gcd(252, 105)

Each row replaces the previous pair: (252, 105) → (105, 42) → (42, 21) → (21, 0). The GCD is the last divisor that divided exactly.

Try it yourself 🧮

Type any two numbers (1 to 9 999) and watch the algorithm run.

Exercises 🎯