GCD and LCM Calculator
| n | Prime factorisation |
|---|---|
| 12 | 2 × 2 × 3 |
| 36 | 2 × 2 × 3 × 3 |
| 60 | 2 × 2 × 3 × 5 |
| 84 | 2 × 2 × 3 × 7 |
| 100 | 2 × 2 × 5 × 5 |
| 144 | 2 × 2 × 2 × 2 × 3 × 3 |
| 360 | 2 × 2 × 2 × 3 × 3 × 5 |
| 1024 | 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 |
The greatest common divisor (GCD) and least common multiple (LCM) are the two numbers that control how fractions add, gears mesh and calendars align. This calculator runs the Euclidean algorithm - the oldest recorded algorithm, from Euclid’s Elements around 300 BC - and shows the prime factorisation of both inputs so you can see why the answer is what it is.
The identity GCD(a,b) × LCM(a,b) = a × b connects the two: once you know one, the other is division. It is the reason the LCM of 12 and 18 is 36, not 216.
How to use
- Enter two non-negative integers; the GCD, LCM and prime factorisations appear instantly.
- Use the coprime chip to see what happens when GCD = 1 (no shared prime factors).
- Check the table for the prime factorisations of common numbers - the building blocks of the GCD and LCM.
Frequently asked questions
What is the Euclidean algorithm?
It finds the GCD by repeatedly replacing the larger number with the remainder of dividing it by the smaller, until the remainder is zero. The last non-zero divisor is the GCD. For GCD(48,18): 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so GCD = 6. It works because any common divisor of a and b also divides a mod b.
Why is GCD(a,b) × LCM(a,b) = a × b?
Because the GCD takes the minimum power of each shared prime while the LCM takes the maximum - and min + max = the total power in a × b. For 12 = 2²×3 and 18 = 2×3²: GCD = 2×3 = 6 (min powers), LCM = 2²×3² = 36 (max powers), and 6 × 36 = 216 = 12 × 18.
What are coprime numbers?
Two numbers are coprime (or relatively prime) when their GCD is 1 - they share no prime factors. 17 and 5 are coprime. Coprime numbers are why the LCM of two coprime numbers equals their product: with no shared primes, the LCM must take every prime at full power from both.
How is GCD used in real life?
Simplifying fractions (divide top and bottom by the GCD), arranging objects into equal grids (the GCD is the largest square tile that evenly tiles a rectangle), and cryptography (the extended Euclidean algorithm computes modular inverses for RSA key generation).