GCD and LCM calculator with steps
Find the greatest common divisor and least common multiple of any list of numbers, with Euclidean algorithm steps and prime factorisations.
- Runs in your browser
- Nothing you enter is sent
- Free, no account
Greatest common divisor (GCD)
Least common multiple (LCM)
Numbers
48, 180, 210
Coprime?
No
they share the factor 6
Reduced ratio
8 : 30 : 35
each number divided by the GCD
Euclidean algorithm for 48 and 180
| Step | a | b | a ÷ b | Remainder |
|---|---|---|---|---|
| 1 | 48 | 180 | 0 | 48 |
| 2 | 180 | 48 | 3 | 36 |
| 3 | 48 | 36 | 1 | 12 |
| 4 | 36 | 12 | 3 | 0 |
The algorithm stops when the remainder reaches zero; the divisor at that point is the GCD.
Prime factorisations
| Number | Prime factorisation | Divisors |
|---|---|---|
| 48 | 2⁴ × 3 | 10 |
| 180 | 2² × 3² × 5 | 18 |
| 210 | 2 × 3 × 5 × 7 | 16 |
Step-by-step working
Run the Euclidean algorithm on the first two numbers.
48 = 0 × 180 + 48 180 = 3 × 48 + 36 48 = 1 × 36 + 12 36 = 3 × 12 + 0The last non-zero remainder is the GCD of 48 and 180: 12.
Fold the running GCD against each remaining number.
GCD(12, 210) = 6GCD is associative, so taking them two at a time gives the GCD of the whole list.
Cross-check with prime factorisation.
48 = 2⁴ × 3 180 = 2² × 3² × 5 210 = 2 × 3 × 5 × 7GCD takes the lowest power of every prime that appears in all of them.
GCD = 2 × 3 = 6LCM takes the highest power of every prime that appears anywhere.
LCM = 2⁴ × 3² × 5 × 7 = 5040Check the identity that links the two for a pair.
GCD(48, 180) × LCM(48, 180) = 12 × 720 = 8640 = 48 × 180This identity only holds for two numbers at a time — it does not extend to three or more.
How to use it
Type two or more whole numbers separated by commas, spaces or newlines. The greatest common divisor and least common multiple appear immediately, together with the Euclidean algorithm table for the first pair, the prime factorisation of every input, and the step-by-step reasoning for both answers.
Negative signs are ignored — GCD and LCM are defined on magnitudes, so GCD(−12, 18) is the same as GCD(12, 18).
What the two quantities mean
- Greatest common divisor (GCD) — the largest whole number that divides all of your inputs exactly. Also called the greatest common factor (GCF) or highest common factor (HCF); the three names are completely interchangeable.
- Least common multiple (LCM) — the smallest positive number that all of your inputs divide into exactly.
If the GCD is 1, the numbers are coprime: they share no prime factor, even though neither has to be prime itself. 8 and 9 are coprime.
The Euclidean algorithm
This is the oldest algorithm still in everyday use, and it is beautifully simple: divide the larger number by the smaller, keep the remainder, and repeat with the smaller number and that remainder. When the remainder hits zero, the last non-zero divisor is the GCD.
For 1071 and 462:
| a | b | a ÷ b | Remainder |
|---|---|---|---|
| 1071 | 462 | 2 | 147 |
| 462 | 147 | 3 | 21 |
| 147 | 21 | 7 | 0 |
The remainder reached zero with a divisor of 21, so GCD(1071, 462) = 21. It works because any number dividing both a and b must also divide their remainder, so the pair can be shrunk without changing the answer. The number of steps grows only logarithmically, which is why it handles hundred-digit inputs instantly.
The prime factorisation method
Factor each number into primes, then:
- GCD — take the lowest power of each prime that appears in every number.
- LCM — take the highest power of each prime that appears in any number.
For 48 = 2⁴ × 3 and 180 = 2² × 3² × 5: the GCD takes 2² × 3 = 12, and the LCM takes 2⁴ × 3² × 5 = 720. This method is slower for large numbers, because factoring is hard, but it makes the answer obvious and it is the method most classrooms teach. The tool shows both.
The identity linking them
For any two numbers, GCD(a, b) × LCM(a, b) = a × b. So once you have the GCD, the LCM is just a × b ÷ GCD — which is how the calculator computes it, avoiding the need to factor anything. Note the identity holds for pairs only. For three or more numbers you must fold pairwise: LCM(a, b, c) = LCM(LCM(a, b), c).
Where you actually need these
- Adding fractions — the LCM of the denominators is the least common denominator, which keeps the numbers small.
- Simplifying fractions and ratios — dividing by the GCD reduces to lowest terms in one step.
- Repeating schedules — two buses leaving every 12 and 18 minutes coincide every LCM(12, 18) = 36 minutes.
- Tiling and packing — the largest square tile that fits a 48 × 180 cm floor exactly has side GCD(48, 180) = 12 cm.
- Gears and pulleys — two gears with 8 and 12 teeth return to their starting alignment after LCM(8, 12) = 24 teeth pass.
- Cryptography — RSA key generation uses the GCD to test that the public exponent is coprime to Euler’s totient.
Quick reference
| Numbers | GCD | LCM |
|---|---|---|
| 12, 18 | 6 | 36 |
| 8, 9 | 1 (coprime) | 72 |
| 48, 180 | 12 | 720 |
| 15, 25, 35 | 5 | 525 |
| 4, 6, 8, 12 | 2 | 24 |
| 1071, 462 | 21 | 23,562 |
Precision and privacy
GCD and LCM use arbitrary-precision integers, so inputs of any practical length are exact. Prime factorisation is attempted only for values small enough to factor by trial division quickly. Everything runs inside your browser and nothing is uploaded.
Questions
What is the difference between GCD, GCF and HCF?
They are three names for the same thing: the largest whole number that divides all your inputs. Greatest common divisor, greatest common factor and highest common factor are interchangeable.
How does the Euclidean algorithm work?
Repeatedly replace the larger number with the remainder of dividing it by the smaller one. When the remainder hits zero, the last non-zero value is the GCD. Every division is listed.
How is the LCM of more than two numbers found?
Pairwise, left to right, using LCM(a, b) = a × b ÷ GCD(a, b). The tool also shows the prime-factor method, taking the highest power of each prime that appears.
Can it handle very large numbers?
GCD and LCM use arbitrary-precision integers, so hundred-digit inputs are fine. Prime factorisation is only attempted for values small enough to factor quickly.