LCM & GCD
Least common multiple & GCD
About This Calculator
The Greatest Common Divisor (GCD) is the largest number that divides both a and b without remainder, useful for simplifying fractions. The Least Common Multiple (LCM) is the smallest number that both a and b divide into evenly, essential for adding fractions. The two are linked by the relationship LCM(a,b) = (a × b) / GCD(a,b).
Formula
GCD via Euclidean algorithm: GCD(a, b) = GCD(b, a mod b) until b = 0
LCM(a, b) = (a × b) / GCD(a, b)
Example Calculation
Find GCD and LCM of 48 and 18.
- GCD(48, 18): 48 mod 18 = 12; GCD(18, 12): 18 mod 12 = 6; GCD(12, 6) = 6
- LCM(48, 18) = (48 × 18) / 6 = 864 / 6 = 144
GCD(48, 18) = 6; LCM(48, 18) = 144
GCD and LCM Examples
| a | b | GCD(a,b) | LCM(a,b) |
|---|---|---|---|
| 12 | 8 | 4 | 24 |
| 15 | 10 | 5 | 30 |
| 24 | 36 | 12 | 72 |
| 7 | 13 | 1 | 91 |
| 48 | 18 | 6 | 144 |
| 100 | 75 | 25 | 300 |
Frequently Asked Questions
What does GCD = 1 mean?
When GCD(a, b) = 1, the numbers are called coprime or relatively prime — they share no common factors other than 1. For example, 8 and 15 are coprime.
Why is LCM useful?
LCM is used to find the lowest common denominator when adding or comparing fractions. For 1/4 + 1/6, the LCM of 4 and 6 is 12, so you convert to 3/12 + 2/12.
How does the Euclidean algorithm work?
Repeatedly replace the larger number with the remainder of dividing the two numbers until the remainder is 0. The last non-zero remainder is the GCD. It is very efficient even for large numbers.