The site's first entry under a new category, Number Theory — algorithms about the
integers themselves rather than arrays, graphs, or strings. The question here: given two whole numbers
a and b, what's the largest number that divides both, with no remainder? That's
the greatest common divisor, gcd(a, b) — the same operation you may already have seen
mentioned in passing as a valid Segment Tree combining
rule alongside min, max, and sum. It's also how you'd reduce a fraction like 462/1071 to lowest terms, or
check whether two gear ratios ever return to their starting alignment.
Euclid described this method in Book VII of the Elements, around 300 BCE — it's one of the oldest algorithms still used unmodified in production code today. The insight: gcd(a, b) is unaffected by replacing the larger number with its remainder after dividing by the smaller. Repeat that swap-and-reduce step and the pair shrinks every time until one side hits zero, at which point the other side is the answer.
Enter any two whole numbers (negative is fine — the algorithm strips the sign before starting) and step through the reduction. 1071, 462 is the classic textbook pair; 89, 55 is a worst case in disguise — two consecutive Fibonacci numbers, which force the maximum possible number of steps for numbers their size (see Complexity).
(a, b) pairs, oldest to newest:
The whole algorithm rests on one fact: gcd(a, b) = gcd(b, a mod b). Write
a = b·q + r where r = a mod b (that's just what division with remainder means).
Any number that divides both a and b also divides a - b·q, which is
exactly r — so every common divisor of (a, b) is a common divisor of
(b, r). Run the same argument in reverse (a = b·q + r also means r = a -
b·q divides back up) and it holds both ways: (a, b) and (b, r) have
exactly the same set of common divisors, so they share the same greatest one.
gcd(a, b) = gcd(b, a mod b) for b > 0
gcd(a, 0) = a base caseTermination follows because a mod b is always strictly smaller than b, and
never negative once both inputs are non-negative — so the second number in the pair strictly decreases
every step while staying ≥ 0, and a strictly decreasing sequence of non-negative integers can't run
forever. Notice the algorithm doesn't care which input started larger, either: if a < b,
the first step's quotient is just 0 and a mod b = a, which swaps the pair into the expected
order for free — no separate ordering check needed, as the demo's own remainder line makes visible on the
first step of any pair entered backwards.
function gcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}Skipping Math.abs doesn't just flip the sign wrong — it flips it
unpredictably. JavaScript's % is a remainder operator, not a true mathematical
modulo: the result's sign always follows the dividend, not a fixed rule. Drop the
Math.abs calls from the reference implementation above and run it on three inputs that only
differ in which side is negative:
gcd(48, -18) === -6 // sign wrong: mathematically gcd is 6
gcd(-48, -18) === -6 // sign wrong: mathematically gcd is 6
gcd(-48, 18) === 6 // sign happens to come out rightChecked exhaustively over every integer pair in [-40, 40]² (excluding (0, 0)): the
magnitude the unmodified loop returns always matches the true gcd — there's no case where it
loops forever or lands on the wrong number entirely — but the sign depends on which operand was
negative in a way that isn't a simple "negate if either input was negative" rule, so a caller trusting the
sign of the raw result can silently get burned. The fix isn't patching the sign afterward; it's making both
inputs non-negative once, up front, exactly as the reference implementation does — after that, every
intermediate remainder the loop touches is provably non-negative too.
Repeated subtraction is also "correct" — and catastrophically slower on skewed inputs, not just a little slower. Before Euclid's remainder version, the older textbook description just subtracts the smaller number from the larger, repeatedly, until they're equal:
function gcdSubtractive(a, b) {
while (a !== b) {
if (a > b) a -= b; else b -= a;
}
return a;
}It's correct — subtraction is just division's quotient forced to be 1 every step instead of the true
quotient q — but that's exactly the problem. On gcd(1, 1000000), the modulo
version above finishes in 2 steps (1000000 mod 1 = 0 immediately makes
b zero). The subtractive version takes 999,999 steps, subtracting 1 from
1,000,000 nearly a million times before the two sides finally meet at 1. Both correctly return
1 — the subtractive version just pays for it with roughly half a million times more
work, and the gap gets worse the more lopsided the two inputs are, not better.
O(log(min(a, b))) division steps — and the bound isn't loose, it's tight, with a known
worst case. Consecutive Fibonacci numbers are the slowest possible input for their size:
each step's quotient is forced to be exactly 1 (since F(k) = 1·F(k-1) + F(k-2)), so the pair
shrinks as slowly as the algorithm allows. A brute-force check of every pair (a, b) with
1 ≤ b ≤ a < 100 confirms it directly: (89, 55) — the two Fibonacci numbers
under 100 — takes 9 division steps, more than any other pair in that entire range,
matching the demo's own fib preset above. This is Lamé's theorem: since Fibonacci numbers grow
exponentially, forcing the algorithm's worst case to take that many steps means the number of steps can
only ever grow logarithmically with the input size — the same shape as binary search's narrowing, though
the mechanism (shrinking a remainder instead of halving a range) is unrelated.
This page finds whether a and b share a divisor and how large it is, but not which integers combine a and b to produce it. See the Extended Euclidean Algorithm for that: the same reduction loop, carrying two extra running numbers, that also finds x and y with a·x + b·y = gcd(a, b) — and, from there, modular inverses.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other thirteen Number Theory entries side by side.