GCD / LCM
Greatest common divisor and LCM
About This Calculator
The Greatest Common Divisor (GCD) is the largest number that divides two integers without remainder, used for simplifying fractions. The Least Common Multiple (LCM) is the smallest number both integers divide into evenly, essential for adding fractions with different denominators.
Formula
GCD via Euclidean algorithm: GCD(a,b) = GCD(b, a mod b), stop when remainder = 0
LCM(a,b) = (a * b) / GCD(a,b)
Example Calculation
Find GCD and LCM of 252 and 105
- 252 = 2*105 + 42 → GCD(105, 42)
- 105 = 2*42 + 21 → GCD(42, 21)
- 42 = 2*21 + 0 → GCD = 21; LCM = 252*105/21 = 1260
GCD(252, 105) = 21; LCM(252, 105) = 1260
GCD and LCM for Common Pairs
| a | b | GCD | LCM |
|---|---|---|---|
| 12 | 8 | 4 | 24 |
| 18 | 12 | 6 | 36 |
| 252 | 105 | 21 | 1260 |
| 100 | 75 | 25 | 300 |
| 48 | 36 | 12 | 144 |
| 35 | 14 | 7 | 70 |
Frequently Asked Questions
How do I use GCD to simplify a fraction?
Divide both numerator and denominator by their GCD. For example, 36/48: GCD(36,48)=12, so 36/48 = (36/12)/(48/12) = 3/4.
Why is the Euclidean algorithm so efficient?
Each step reduces the larger number significantly. For any two n-digit numbers, the algorithm takes at most 5n steps. This makes it practical even for very large numbers used in cryptography.
What does it mean for two numbers to be coprime?
Two numbers are coprime (relatively prime) if their GCD = 1. They share no common prime factors. For example, 8 and 15 are coprime (GCD=1), even though neither is prime.