GCD and LCM calculator
Enter two or more whole numbers. You get their greatest common divisor and least common multiple, each step of the Euclidean algorithm and the prime factorization of every number.
Runs in your browser: nothing you enter is sent anywhere.
How to use it
- Type 2 to 20 whole numbers, each below one trillion (10¹²), separated by commas, spaces or new lines.
- The GCD and LCM appear at once, followed by the Euclidean algorithm and the prime factorizations.
How it works
Euclidean algorithm. For two numbers a > b, write a = q × b + r and continue with b and r until the remainder is 0. The last divisor is the GCD.
Prime factors. GCD = product of common primes with the lowest powers; LCM = product of all primes with the highest powers. For two numbers there is also a shortcut: LCM(a, b) = a × b ÷ GCD(a, b).
The LCM is calculated with exact integer arithmetic, so even an LCM with dozens of digits is exact.
Worked example
84, 120 and 36:
- Euclid: 120 = 1 × 84 + 36, 84 = 2 × 36 + 12, 36 = 3 × 12 + 0, so GCD(84, 120) = 12; then 36 = 3 × 12 + 0, so the GCD of all three is 12.
- Factors: 84 = 2² × 3 × 7, 120 = 2³ × 3 × 5, 36 = 2² × 3².
- GCD = 2² × 3 = 12. LCM = 2³ × 3² × 5 × 7 = 2520.
Where you need it
- Fractions. The GCD simplifies a fraction (84/120 = 7/10 after dividing by 12); the LCM of the denominators is the least common denominator.
- Schedules. Buses every 12 and 18 minutes leave together again after LCM(12, 18) = 36 minutes.
- Tiling and cutting. The largest square tile that fits a 84 × 120 cm area exactly is GCD = 12 cm.
Frequently asked questions
What are the GCD and the LCM?
The greatest common divisor (also called the greatest common factor, GCF, or highest common factor, HCF) is the largest number that divides all the given numbers. The least common multiple is the smallest positive number that all of them divide.
How does the Euclidean algorithm work?
Divide the larger number by the smaller and keep the remainder. Then divide the smaller number by that remainder, and repeat. The last non-zero remainder is the GCD. For 120 and 84 the remainders are 36, 12 and 0, so the GCD is 12.
How do I get the GCD and LCM from prime factors?
Write each number as a product of primes. The GCD takes only the primes that all numbers share, each with its lowest power; the LCM takes every prime that appears, each with its highest power.
What about three or more numbers?
The GCD is found pair by pair, GCD(a, b, c) = GCD(GCD(a, b), c), and the same goes for the LCM. The calculator shows the Euclid steps for each pair.
What about negative numbers and zero?
Signs are ignored, because divisors of −12 and 12 are the same. GCD(0, n) is n, the LCM of any list that contains 0 is 0, and the GCD of only zeros is not defined.