cf.completefrontend
MATH & GEOMETRY · FOUNDATION

Euclid's greatest common divisor

Find the largest number that divides two numbers by repeatedly replacing the pair with the smaller number and the remainder.

Time O(log(min(a, b)))Space O(1)4 practice problemsStep-through picture

The idea

The greatest common divisor (GCD) of two whole numbers is the largest number that divides both with nothing left over. The GCD of 48 and 18 is 6: both are multiples of 6, and no larger number divides both.

Euclid's method finds it without listing divisors. It uses one fact: any number that divides both a and b also divides the remainder a % b. So the pair (a, b) has the same GCD as the pair (b, a % b). The remainder is always smaller than b, so the numbers shrink fast. When the remainder reaches 0, the other number is the GCD.

The GCD unlocks a second tool, the least common multiple (LCM): the smallest number that both divide. lcm(a, b) = a / gcd(a, b) * b. Simplifying fractions, aspect ratios, and finding when two repeating cycles line up all use these two.

An everyday example

Tiling a floor with the largest square tile

You want to cover a 48 by 18 floor with square tiles, all the same size, with no cutting. First, lay the biggest squares you can: 18 by 18 squares fit twice, leaving a 12 by 18 strip. The tile that works for the whole floor must also work for that strip. In the strip, 12 by 12 squares fit once, leaving 12 by 6. Then 6 by 6 squares fill 12 by 6 exactly. So 6 by 6 is the largest tile that covers the whole floor.

How the example maps to the code
In the exampleIn the code
The two sides of the floora and b
The strip left after laying the big squaresremainder = a % b
Moving on to tile the leftover stripa = b; b = remainder
The squares fill the strip exactlyb === 0, so the answer is a

From the slow way to euclid's greatest common divisor

  1. Start with the obvious way: try every candidate from the smaller number down to 1, and stop at the first one that divides both. For 630 and 2002 that takes 617 tries before it reaches 14. For two numbers near a billion it can take a billion tries, so we need something that doesn't walk through every candidate.
  2. Here is the useful fact. If d divides both a and b, it also divides their difference a - b, because a - b is a multiple of d minus another multiple of d. So the pair (2002, 630) has the same common divisors as (1372, 630). Subtracting the smaller number from the bigger one shrinks the pair without changing the answer.
  3. Subtracting can still be slow. From 2002 we subtract 630 three times (1372, 742, 112) before the number drops below 630. Subtracting b from a until the result is smaller than b is exactly what the remainder does in one step: 2002 % 630 is 112. So replace the pair (a, b) with (b, a % b).
  4. Each new remainder is smaller than the number it was divided by, so the pair keeps shrinking until the second number is 0. Every number divides 0, so the common divisors of (a, 0) are just the divisors of a, and the greatest one is a itself. Take Math.abs first so signs don't matter, and repeat the remainder step while b !== 0. That loop is Euclid's algorithm.

How it works

  1. Make both numbers non-negative with Math.abs, because the GCD doesn't depend on the sign.
  2. While b is not 0, compute remainder = a % b.
  3. Move the pair along: a becomes b, and b becomes remainder.
  4. When b is 0, a is the GCD. Return it.
  5. For the LCM, divide one number by the GCD first, then multiply: a / gcd(a, b) * b.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function gcd(a, b) {
  2. a = Math.abs(a);
  3. b = Math.abs(b);
  4. while (b !== 0) {
  5. const remainder = a % b;
  6. a = b;
  7. b = remainder;
  8. }
  9. return a;
  10. }
  12. function lcm(a, b) {
  13. if (a === 0 || b === 0) return 0;
  14. return Math.abs((a / gcd(a, b)) * b);
  15. }

How fast it is

TimeO(log(min(a, b)))
Extra memoryO(1)

The larger number at least halves every two steps, so the loop runs a number of times that grows with the digits of the numbers. Only two numbers are stored.

  • Best caseO(1)

    b is 0, so the loop never runs, or b divides a at once, like gcd(2002, 14), which needs one step.

  • Average caseO(log n)

    Random pairs of numbers below a million take about 12 steps, and below a billion about 18. The count grows with the number of digits.

  • Worst caseO(log n)

    Two neighboring Fibonacci numbers, like 987 and 610. Every quotient is 1, so the pair shrinks as slowly as possible: 14 steps here, and at most 76 steps for any numbers JavaScript stores exactly.

Common mistakes

  • Computing the LCM as a * b / gcd(a, b). The product a * b can pass 2^53 and lose precision even when the LCM itself is small. Divide first: a / gcd(a, b) * b.
  • Looping from min(a, b) down to 1 to find the GCD. It works, but takes up to a billion steps for large numbers.
  • Forgetting Math.abs. With negative numbers the result can come out negative.
  • Stopping when a % b === 0 and returning a instead of b. The divisor is the smaller number of the pair.

When to use it

Look for these clues in a problem:

  • The problem asks for the largest size, step, or unit that divides several numbers evenly.
  • You need to simplify a fraction or a ratio, such as 1920:1080 to 16:9.
  • Two or more things repeat on different cycles and you need when they line up again (that's the LCM).
  • A grid or layout must split evenly into equal tiles.

Check yourself

Answer each one in your head first, then open it.

What happens if a is smaller than b at the start?

Nothing special: a % b is just a, so the first step swaps the pair. The code needs no extra check for it.

Why do the numbers 987 and 610 need more steps than most pairs their size?

They are neighboring Fibonacci numbers, so every quotient is 1 and each remainder is as large as it can be. The pair shrinks as slowly as possible: 14 steps.

Why does lcm divide by the GCD before multiplying?

Because a / gcd(a, b) is a whole number and keeps the result small. Multiplying first can make a product above 2^53, which JavaScript can't store exactly.

Why must the loop stop at b === 0 rather than when a % b === 0?

Stopping when a % b === 0 also works, but then the answer is b, not a, and returning a is a common bug. Running one more step moves that value into a, so the code can always return a.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one promise, true at the top of every loop: the pair (a, b) has exactly the same common divisors as the two original numbers. At the start it's true, because Math.abs doesn't change which numbers divide a value.

Each step keeps the promise. Write a = q × b + remainder. In the trace, 14 divides 2002 and 630, so it divides 2002 - 3 × 630 = 112. Going the other way, anything that divides 630 and 112 also divides 3 × 630 + 112 = 2002. So swapping (2002, 630) for (630, 112) neither adds nor loses a common divisor.

The loop always ends, because remainder is always smaller than b, and a non-negative whole number can't get smaller forever. It also ends fast: within two steps the first number at least halves. If b <= a / 2, the remainder is below b, so below a / 2. If b > a / 2, then a % b = a - b, which is also below a / 2.

When the loop stops, the pair is (a, 0). The common divisors of a and 0 are all the divisors of a, and the greatest of those is a. Since the promise says these are the same common divisors as the original numbers, returning a gives the right answer.

Going deeper

3 more ideas

Why the remainder keeps the same GCD

Write a = q × b + r, where r = a % b. If a number d divides both a and b, it divides q × b, so it also divides a - q × b, which is r. And if d divides b and r, it divides q × b + r = a. So (a, b) and (b, r) have exactly the same common divisors, and the same greatest one.

Why it's so fast

Every two steps, the larger number at least halves. So the number of steps grows with the number of digits, not with the size of the numbers: about O(log(min(a, b))). Even two numbers near a billion need only a few dozen steps.

Edge cases: zero, negatives, and more than two numbers

gcd(a, 0) is a, because every number divides 0. gcd(0, 0) is 0 by convention. Negative inputs give the same GCD as their absolute values. For a list, fold it: gcd(gcd(gcd(x1, x2), x3), x4), since the GCD of many numbers is built one pair at a time.

Work it by hand

Every step in a table, with why

Find gcd(-630, 2002). The first number is negative and smaller than the second, so the trace shows both of those being handled.

a = -630, b = 2002

StepabremainderWhat happensWhy
16302002-Math.abs on bothThe sign is dropped, because -630 and 630 have the same divisors.
26302002630pair becomes (2002, 630)630 % 2002 is 630, because 2002 doesn't fit into 630 even once. So the first step just swaps the two numbers.
32002630112pair becomes (630, 112)2002 = 3 × 630 + 112. One remainder does the work of three subtractions.
463011270pair becomes (112, 70)630 = 5 × 112 + 70. The pair is now far smaller than where it started.
51127042pair becomes (70, 42)112 = 1 × 70 + 42. A quotient of 1 is the slowest kind of step: the numbers shrink only a little.
6704228pair becomes (42, 28)70 = 1 × 42 + 28. Another slow step.
7422814pair becomes (28, 14)42 = 1 × 28 + 14.
828140pair becomes (14, 0)28 = 2 × 14 + 0. The remainder is 0, so 14 divides 28 exactly.
9140-b === 0: return 14The loop condition fails. Every number divides 0, so the answer is a.

The GCD is 14, found in 7 loop steps instead of 617 tries. Then lcm(-630, 2002) divides first: 630 / 14 = 45, and 45 × 2002 = 90090.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Euclid's greatest common divisorO(log n)O(1)Almost always: it's short, exact, and fast for any size of whole number.
Count down from the smaller numberO(n)O(1)Only for tiny numbers in throwaway code. It takes up to min(a, b) tries.
Compare prime factorizationsO(√n)O(log n)When you need the factorizations anyway, for example to count divisors. Factoring is much slower than Euclid for large numbers.

Extra memory: O(1): two numbers and a remainder. A recursive version, gcd(b, a % b), uses O(log n) space for its call stack.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Euclid's greatest common divisor and the other approaches, on a scale where each line up is 10 times more steps.
  • Euclid's greatest common divisor O(log n)
  • Count down from the smaller number O(n)
  • Compare prime factorizations O(√n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Euclid's greatest common divisor31020
Count down from the smaller number101,0001 million
Compare prime factorizations3321,000

Inputs that need care

6 tricky inputs
Both zero: gcd(0, 0)
The loop never runs and it returns 0. Every number divides 0, so there is no greatest one; returning 0 is the usual rule. lcm returns 0 before calling gcd.
One zero: gcd(0, 9)
The first step computes 0 % 9 = 0, so the pair becomes (9, 0) and it returns 9. gcd(9, 0) returns 9 without looping.
Negative numbers: gcd(-630, 2002)
Math.abs makes both positive first, so the answer is 14, never -14.
The smaller number first: gcd(630, 2002)
No swap is needed. The first remainder is 630 % 2002 = 630, which moves the pair to (2002, 630) by itself.
Decimals: gcd(0.3, 0.1)
The code expects whole numbers. Decimal remainders aren't exact, so it returns about 2.8e-17 instead of 0.1. Scale decimals to whole numbers first, such as cents instead of dollars.
A big LCM: lcm(6451993423, 4212802097)
The product a * b is far past 2^53, so a * b / gcd comes out as 3949000642487957.5, a fraction. Dividing first gives the exact 3949000642487957.

Variations and follow-ups

Twists interviewers add

Extended Euclid

Keep track of how each remainder is built from the original a and b, and you also get whole numbers x and y with a × x + b × y = gcd(a, b). When the GCD is 1, x is the modular inverse of a modulo b. This works even when the modulus isn't prime, where Fermat's shortcut doesn't.

GCD of a whole list

Fold the list one pair at a time: values.reduce((g, v) => gcd(g, v), 0). Starting at 0 works because gcd(0, v) is v. You can stop early once the running GCD is 1, since nothing can make it smaller.

Binary GCD

Stein's method replaces % with halving and subtraction: pull out shared factors of 2, then subtract the smaller odd number from the larger. It uses only shifts and subtraction, which can be faster for very large BigInt values where division is costly.

Recursive form

gcd(a, b) is a when b is 0, and gcd(b, a % b) otherwise. It's a one-line definition that matches the proof exactly. The loop version does the same steps without growing the call stack.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from words like "simplify the fraction", "aspect ratio", "largest square tile that fits", "largest group size that divides both", or "when do two repeating cycles line up again" (that last one is the LCM).
  • Explain it in two sentences: "(a, b) and (b, a % b) have the same common divisors, so I can keep replacing the pair. The numbers at least halve every two steps, so it's O(log n)."
  • Test by hand: gcd(0, 5), gcd(5, 0), a negative input, and the smaller number first. Each one takes a line of thought, and each one shows a different part of the code doing its job.
  • The usual follow-up is the LCM. Say "divide before multiplying" and write a / gcd(a, b) * b, explaining that a * b can pass 2^53 even when the LCM fits.

Where frontend code uses it

The same idea in real UI code
  • Showing an aspect ratio: 1920 × 1080 divided by their GCD 120 gives 16:9, which an image editor or a video settings panel can display.
  • CSS animations with different durations, such as 400ms and 600ms, line up again after their LCM, 1200ms. Knowing that tells you when a combined loop repeats.
  • Design tools that snap elements to a shared spacing unit can use the GCD of the spacings in a layout.

Related algorithms