GCD & LCM
GCD and LCM calculator
The greatest common divisor and least common multiple of two to ten whole numbers, with Euclid's algorithm written out step by step.
GCD (HCF)42
LCM1,260
The largest number that divides 84, 126 and 210 exactly is 42.
Euclid's algorithm, step by step
Step 1: gcd(84, 126)
- 126=1 × 84+42
- 84=2 × 42+0
The last non-zero remainder is the GCD: 42.
Step 2: gcd(42, 210)
- 210=5 × 42+0
The last non-zero remainder is the GCD: 42.
LCM from the GCD
- lcm(84, 126) = 84 × 126 ÷ 42 = 252
- lcm(252, 210) = 252 × 210 ÷ 42 = 1,260
Check with prime factors
- 84 = 22 × 3 × 7
- 126 = 2 × 32 × 7
- 210 = 2 × 3 × 5 × 7
The GCD takes each prime to its lowest power in the list: 2 × 3 × 7 = 42. The LCM takes each prime to its highest power: 22 × 32 × 5 × 7 = 1,260.
Two ways to the same answer
The greatest common divisor (GCD, also called the highest common factor) is the largest number that divides every number in your list exactly. The least common multiple (LCM) is the smallest positive number that all of them divide into.
Euclid's algorithm finds the GCD without factoring anything. Divide the larger number by the smaller and keep the remainder, then divide the last divisor by that remainder, and repeat until the remainder is 0. The last divisor is the GCD. It works because anything that divides a and b also divides a − q × b, the remainder. It is fast as well: the number of steps grows only with the number of digits.
1071 = 2 × 462 + 147 → 462 = 3 × 147 + 21 → 147 = 7 × 21 + 0, so gcd = 21
For three or more numbers the steps are chained, gcd(a, b, c) = gcd(gcd(a, b), c), and the LCM follows from lcm(a, b) = a × b ÷ gcd(a, b), chained the same way.
With small numbers you can also compare prime factorizations: the GCD keeps each shared prime at its lowest power, the LCM keeps every prime at its highest. The calculator adds that check when all numbers are below 1015.
Sources
- Euclid, Elements, Book VII, Proposition 2 (finding the greatest common measure), in David E. Joyce's online edition.
- Knuth DE. The Art of Computer Programming, Vol. 2, §4.5.2 (the greatest common divisor), and Euclidean algorithm on step counts and Bézout's identity.
Questions
What does coprime mean?
Numbers are coprime when their GCD is 1, like 8 and 15; neither has to be prime. A list can be coprime while some pairs share a factor: 6, 10 and 15 have GCD 1, yet each pair shares 2, 3 or 5.
What are the GCD and LCM when one number is 0?
gcd(n, 0) = n, because every number divides 0, and lcm(n, 0) = 0. gcd(0, 0) is written as 0 by convention.
Where are GCD and LCM used?
Simplifying fractions (divide top and bottom by the GCD), adding fractions (the LCM of the denominators is the lowest common denominator), lining up repeating cycles such as gear teeth or timetables, and RSA cryptography, which uses Bézout's coefficients to build keys.