GCD and LCM Calculator
Greatest common divisor and least common multiple of up to twenty whole numbers of any size, with Euclid’s steps and prime factors.
Answer
- Least common multiple
- 180
Prime factors
- 12 = 2² × 3
- 18 = 2 × 3²
- 30 = 2 × 3 × 5
The GCD takes each shared prime at its lowest power; the LCM takes every prime at its highest.
Euclid’s steps
- 18 = 1 × 12 + 6
- 12 = 2 × 6 + 0
- GCD(12, 18) = 6
- 30 = 5 × 6 + 0
- GCD(6, 30) = 6
- Found by Euclid’s algorithm, worked in exact whole numbers of any length. For more than two numbers, the GCD is found one pair at a time: GCD(a, b, c) = GCD(GCD(a, b), c).
Numbers
How is this calculated?
Euclid: GCD(a, b) = GCD(b, a mod b), until the remainder is 0 · LCM(a, b) = |a × b| ÷ GCD(a, b) · For more numbers, one pair at a time: GCD(a, b, c) = GCD(GCD(a, b), c)Runs in your browser — nothing you enter leaves this device.
About this tool
What it does
This calculator finds the greatest common divisor (GCD) — also called the highest common factor (HCF) — and the least common multiple (LCM) of two to twenty whole numbers. It shows every step of Euclid’s algorithm, so you can follow or check the working, and for numbers up to fifteen digits it lists the prime factors of each, which shows where both answers come from. The arithmetic is exact for whole numbers of up to 100 digits.
How to use it
- Type two or more whole numbers, separated by commas or spaces.
- Read the GCD and the LCM at the top. "Coprime" means the numbers share no factor other than 1.
- Follow Euclid’s steps: each line divides the larger number by the smaller and keeps the remainder, until the remainder is zero.
- Compare the prime factors: the GCD is every shared prime at its lowest power, the LCM every prime at its highest.
Limits and your data
- Whole numbers only, up to 100 digits each and twenty at a time. Signs are ignored: the GCD and LCM are always given as positive numbers.
- The GCD of 0 and a number is that number, and the LCM of anything with 0 is 0. The GCD of only zeros is not defined.
- Prime factors are listed when every number is non-zero and below 10^15. For larger numbers the Prime Checker factorises one number at a time, with more time to work.
- At most 40 of Euclid’s steps are shown for each pair; the answer is always worked out in full.
- Everything is worked out in this page. Nothing you type is sent anywhere or saved, and it works offline once loaded.
Questions
Is the GCD the same as the HCF?
Yes. Greatest common divisor, highest common factor and greatest common factor (GCF) are three names for the same number: the largest whole number that divides all of them with no remainder.
How does Euclid’s algorithm work?
Divide the larger number by the smaller and keep the remainder. Then divide the smaller number by that remainder, and so on. When the remainder is 0, the last divisor is the GCD. For 1071 and 462: 1071 = 2 × 462 + 147, 462 = 3 × 147 + 21, 147 = 7 × 21 + 0, so the GCD is 21.
How do I find the LCM?
Multiply the two numbers and divide by their GCD. For 4 and 6, the product is 24 and the GCD is 2, so the LCM is 12. With more numbers, repeat it pair by pair.
What is the GCD used for?
Simplifying fractions and ratios: dividing the top and bottom of 18/24 by their GCD, 6, gives 3/4. The LCM gives the common denominator for adding fractions, and answers questions such as when two buses that leave every 12 and every 18 minutes next leave together (after 36 minutes).
What does coprime mean?
Two numbers are coprime when their GCD is 1, such as 8 and 9. They need not be prime themselves; they just share no prime factor.