greatest common divisor

Suppose you have a 12-foot board and an 18-foot board and you want to cut both into equal pieces using the longest possible piece length that leaves no waste. The answer is 6 feet — that is the greatest common divisor of 12 and 18, the biggest number that divides both exactly.

Formally, the greatest common divisor of two integers a and b (not both zero), written gcd(a, b), is the largest positive integer that divides both. One way to compute it is to take the prime factorizations and multiply the primes they share, each raised to the smaller of its two powers. Another, far faster, way is the Euclidean algorithm, which uses repeated division.

A useful boundary case: gcd(a, 0) = a for any positive a, because every number divides 0, so the limiting factor is a itself. When gcd(a, b) = 1 the two numbers share no common factor beyond 1 and are called relatively prime, or coprime — a condition that shows up everywhere from reducing fractions to modular arithmetic.