LCM & GCD Calculator
Calculate the LCM and GCD for two or more numbers using prime factorization.
Essential for adding fractions and solving divisibility problems.
The Greatest Common Divisor (GCD) — also called Greatest Common Factor (GCF) — and the Least Common Multiple (LCM) are two fundamental operations in number theory that appear constantly in fractions, scheduling, tiling, and cryptography.
GCD: The largest number that divides both A and B evenly. LCM: The smallest positive number that is divisible by both A and B.
The key relationship between GCD and LCM: LCM(A, B) = (A × B) / GCD(A, B)
Finding GCD using the Euclidean Algorithm: Repeatedly apply: GCD(A, B) = GCD(B, A mod B) until remainder = 0.
Worked example: Find GCD(48, 18): GCD(48, 18) → 48 mod 18 = 12 → GCD(18, 12) GCD(18, 12) → 18 mod 12 = 6 → GCD(12, 6) GCD(12, 6) → 12 mod 6 = 0 → GCD = 6
LCM(48, 18) = (48 × 18) / 6 = 864 / 6 = 144
Worked example 2: GCD(56, 98): 98 mod 56 = 42 → GCD(56, 42) 56 mod 42 = 14 → GCD(42, 14) 42 mod 14 = 0 → GCD = 14 LCM(56, 98) = (56 × 98) / 14 = 392
Real-world applications:
- Fractions: To add ½ + ⅓, find LCM(2,3) = 6 → convert to 3/6 + 2/6 = 5/6
- Scheduling: Two buses depart every 8 and 12 minutes. LCM(8,12) = 24. They sync every 24 minutes.
- Tiling: To tile a 48×18 floor with square tiles (no cutting), GCD = 6 → use 6×6 tiles (48 tiles total)
- Music: Rhythm patterns of 3 and 4 beats align every LCM(3,4) = 12 beats