GCD and LCM: The Workhorse Twins of Arithmetic

Two small functions quietly do most of the arithmetic that keeps fractions, schedules, and gear ratios honest: the greatest common divisor (GCD) and the least common multiple (LCM). One finds the biggest number that divides into both inputs; the other finds the smallest number both inputs divide into. They look like opposites, and they are connected by a one-line formula — once you see the pairing, half of fraction arithmetic falls into place.

What GCD and LCM actually measure

The greatest common divisor of two numbers is the largest whole number that divides both of them evenly. For 12 and 18, the common divisors are 1, 2, 3, and 6 — so the GCD is 6. It answers "what is the biggest chunk both numbers are built from?"

The least common multiple is the smallest whole number that both numbers divide into evenly. For 12 and 18 the shared multiples start 36, 72, 108, … — so the LCM is 36. It answers "when do these two rhythms first line up?"

GCD(12, 18) = 6   (largest divisor of both)
LCM(12, 18) = 36  (smallest multiple of both)

Notice the mirror image: the GCD lives below the two numbers (6 ≤ 12, 18) and the LCM lives above them (36 ≥ 12, 18). Divisor versus multiple — that is the entire difference.

The Euclidean algorithm: GCD without any factoring

You could find a GCD by listing factors, but the method used for over two thousand years — Euclid's algorithm — never factors anything. It repeatedly replaces the larger number with the remainder of dividing it by the smaller, until the remainder hits zero. The last nonzero number in the chain is the GCD:

GCD(252, 105):
  252 = 2 × 105 + 42
  105 = 2 × 42  + 21
   42 = 2 × 21  +  0   → GCD = 21

Why it works: any number that divides both 252 and 105 must also divide their remainder 42 (since 42 = 252 − 2 × 105), and chasing that logic downward shows the common divisors never change along the chain. Euclid described this in his Elements around 300 BC, which makes it one of the oldest recorded algorithms still in daily use — and it is blazingly fast even on numbers with millions of digits.

The one-line link between the twins

For any two positive numbers, the GCD and LCM are bound together:

GCD(a, b) × LCM(a, b) = a × b

12 × 18 = 216 = 6 × 36   →   LCM(12, 18) = 216 / 6 = 36

So you only ever need to compute one of them. Find the GCD with Euclid's cheap remainder loop, and the LCM comes free by division. Intuitively: a × b counts the shared factors twice (once from each side), so dividing by the GCD removes the double-count and leaves exactly the smallest common multiple.

GCD at work: simplifying fractions

The most everyday use of the GCD is reducing a fraction to lowest terms. Divide top and bottom by their GCD — the value is unchanged because you are multiplying the whole fraction by GCD/GCD = 1:

42/56:  GCD(42, 56):
  56 = 1 × 42 + 14
  42 = 3 × 14 +  0   → GCD = 14
  42/56 = (42 ÷ 14) / (56 ÷ 14) = 3/4

A fraction simplifier does exactly this under the hood, which is why it can always report the unique simplest form rather than just "a smaller-looking" one: the fundamental theorem of arithmetic guarantees only one fully reduced version exists. Simplification also keeps later arithmetic sane — multiplying 3/4 by anything is far easier on the eyes than multiplying 42/56.

LCM at work: adding fractions and lining up schedules

Adding fractions with different denominators requires a common denominator, and the cheapest one is the LCM of the denominators. For 1/6 + 1/8, the LCM of 6 and 8 is 24:

LCM(6, 8) = 6 × 8 / GCD(6, 8) = 48 / 2 = 24
1/6 = 4/24    1/8 = 3/24    →   1/6 + 1/8 = 7/24

You could use 48 (the plain product) instead: 8/48 + 6/48 = 14/48, which then needs reducing by GCD(14, 48) = 2 back down to 7/24. Using the LCM up front means no cleanup step — and with large denominators, keeping the common denominator as small as possible is what keeps the arithmetic manageable.

The same "when do they line up?" logic handles scheduling: two buses leave together, one every 12 minutes and one every 18 minutes, and they next depart together after LCM(12, 18) = 36 minutes. Or a gear with 12 teeth meshing with one of 18 teeth — the same tooth meets again after 36 engagements.

Coprime pairs and a useful extreme

When GCD(a, b) = 1, the numbers are called coprime (or relatively prime) — they share no factor bigger than 1. Coprime pairs sit at the extreme of both formulas: their LCM is simply the product a × b (nothing was double-counted), and any fraction a/b is already in lowest terms. 8 and 9 are coprime even though neither is prime itself — coprimality is about the pair, not the individual numbers. This idea scales up into modular arithmetic and public-key cryptography, where finding two large coprime numbers is a routine construction step.

Try it yourself

The GCD Calculator runs the Euclidean algorithm step by step on any pair of numbers, so you can watch the remainders collapse to zero. Feed the result into the LCM Calculator and confirm the product rule a × b = GCD × LCM on your own pairs. And for the most common practical use, the Fraction Simplifier reduces any fraction to lowest terms and shows the GCD it used — type 42/56 and you should see 3/4 come back.