The greatest common divisor (GCD, also HCF/GCF) is the largest number that divides every value evenly; the least common multiple (LCM) is the smallest number every value divides into. The fast way to the GCD is the Euclidean algorithm — keep replacing the bigger number by the remainder until one hits zero. The LCM then follows for free from GCD(a,b) × LCM(a,b) = a × b. GCD is the engine behind reducing fractions and ratios; LCM is how you find common denominators and line up repeating cycles.
Reviewed: June 20, 2026 · Author: Naveen P N, Founder — AI Calculator · Verified against: the Euclidean algorithm and GCD·LCM identity.
The GCD & LCM rules
The Euclidean algorithm works because any common divisor of a and b also divides their remainder, so the GCD is preserved at each step while the numbers shrink rapidly. Once the GCD is known, the identity GCD·LCM = a·b gives the LCM without extra work. For a list of numbers, both operations are associative, so you combine them two at a time: find the GCD (or LCM) of the first pair, then combine that with the next number, and continue to the end.
Worked example — 12 and 18
GCD by Euclid:
LCM from the identity:
So 12 and 18 have a GCD of 6 and an LCM of 36 — meaning 6 is the largest tile that fits both, and 36 is the first number both divide into. The same routine scales up: 8 and 12 give GCD 4 and LCM 24, while three numbers 4, 6, 8 give GCD 2 and LCM 24 by folding pairwise. When two numbers share no factor — like 7 and 13 — the GCD is 1 (they are coprime) and the LCM is just their product, 91. That coprime case is exactly when a fraction is already in lowest terms.
Frequently Asked Questions
The largest number dividing all values. 12 & 18 → 6. Also called HCF or GCF.
The smallest number all values divide into. 12 & 18 → 36.
Replace the larger by a mod b until 0. 18→6→0, so GCD = 6. Fast for big numbers.
GCD × LCM = a × b (two numbers). 6 × 36 = 216 = 12 × 18.
GCD = 1, no shared factor. 7 & 13 are coprime; LCM = 91 (their product).