GCD & LCM
Find the GCD and LCM of any list of integers, with prime factorizations.
12, 18 — 2 numbers.
The GCD (greatest common divisor) is the largest number that divides every input evenly; the LCM (least common multiple) is the smallest number every input divides into. Since 12 = 2²·3 and 18 = 2·3², GCD(12, 18) = 2·3 = 6 and LCM(12, 18) = 2²·3² = 36.
GCD and LCM from prime factors
Every integer breaks into a unique product of primes. Once you have those factorizations, the GCD is the product of the primes the numbers share, each taken to its lowest power; the LCM is the product of all primes that appear, each taken to its highest power. For 12 = 2²·3 and 18 = 2·3², the shared lowest powers give 2¹·3¹ = 6, and the combined highest powers give 2²·3² = 36.
for two positive integers; extend to a list by folding the operation pairwise
Worked example
Find the GCD and LCM of 12 and 18:
- 1 Factor each number into primes. 12 = 2² · 3 and 18 = 2 · 3².
- 2 GCD: multiply the shared primes at their lowest powers. Both share 2¹ and 3¹, so GCD = 2 · 3 = 6.
- 3 LCM: multiply every prime at its highest power. Take 2² and 3², so LCM = 4 · 9 = 36.
- 4 Check with the product rule. GCD × LCM = 6 × 36 = 216 = 12 × 18, confirming the answer.
GCD and LCM of common pairs
The GCD divides both numbers; the LCM is the smallest multiple of both.
| Pair | Prime factors | GCD | LCM |
|---|---|---|---|
| 12, 18 | 2²·3 and 2·3² | 6 | 36 |
| 8, 12 | 2³ and 2²·3 | 4 | 24 |
| 7, 13 | 7 and 13 | 1 | 91 |
| 15, 25 | 3·5 and 5² | 5 | 75 |
| 6, 10, 15 | 2·3, 2·5, 3·5 | 1 | 30 |
| 4, 6, 8 | 2², 2·3, 2³ | 2 | 24 |
Euclid’s algorithm, coprime numbers, and the product rule
Euclid’s algorithm. You don’t need to factor large numbers to find the GCD. Repeatedly replace the larger number with the remainder of dividing it by the smaller, until the remainder is 0 — the last nonzero value is the GCD. This is fast even for huge inputs.
Coprime numbers. When GCD = 1 the numbers share no common prime factor and are called coprime (or relatively prime). For coprime a and b, the LCM is simply a × b — for example 7 and 13 are coprime, so LCM(7, 13) = 91.
The product rule. For any two positive integers, GCD(a, b) × LCM(a, b) = a × b. That identity is exactly why LCM(a, b) = a × b ÷ GCD(a, b).