LCM and GCD Calculator
Calculate the LCM (Least Common Multiple) and GCD (Greatest Common Divisor) of up to 6 numbers instantly, with step-by-step prime factorization.
Enter Numbers
Enter at least 2 positive integers to compute GCD and LCM.
How It Works
The GCD is computed using the Euclidean algorithm — the oldest known algorithm in mathematics (ca. 300 BC). It repeatedly replaces (a, b) with (b, a mod b) until the remainder is zero; the last non-zero value is the GCD. The LCM of two numbers equals their product divided by their GCD. For more than two numbers, both GCD and LCM are computed pairwise from left to right.
Euclidean Algorithm
GCD (Euclidean): gcd(a,b) = gcd(b, a mod b), repeat until remainder = 0. LCM: lcm(a,b) = (a × b) ÷ gcd(a,b). For multiple numbers: apply pairwise left-to-right.
Example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. LCM(48, 18) = (48 × 18) ÷ 6 = 144.
Key Relationships
- GCD × LCM = a × b
- True for any two positive integers a and b
- GCD(a, 0) = a
- Base case of the Euclidean algorithm
- Coprime numbers
- GCD = 1, so LCM = a × b (no common factors)
- Fractions
- Simplify a/b: divide both by GCD(a, b)
Frequently Asked Questions
What is the difference between GCD and LCM?
GCD (Greatest Common Divisor) is the largest number that divides all the given numbers exactly. LCM (Least Common Multiple) is the smallest number that is divisible by all the given numbers. For two numbers a and b: GCD × LCM = a × b.
When do I need LCM?
LCM is used when adding or subtracting fractions with different denominators — you need the lowest common denominator, which is the LCM of all denominators. It's also used in scheduling problems: e.g., two buses that leave every 12 and 18 minutes will next leave together after LCM(12,18) = 36 minutes.
What is the Euclidean algorithm?
The Euclidean algorithm computes GCD by repeatedly dividing: gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0) = 6. Each step replaces the larger number with the remainder of the division. It is one of the most efficient algorithms for integer arithmetic.
Can GCD simplify fractions?
Yes — divide both numerator and denominator by their GCD to get the simplest form. Example: 36/48 → GCD(36,48) = 12 → 36÷12 / 48÷12 = 3/4.