LCM and GCD Calculator
Find the Least Common Multiple and Greatest Common Divisor of up to 10 numbers
LCM and GCD Explained
The Greatest Common Divisor (GCD), also called the Highest Common Factor (HCF), is the largest number that divides all given numbers exactly. The Least Common Multiple (LCM) is the smallest number that is a multiple of all given numbers.
Methods and Formulas
Real-World Uses
GCD: Simplifying fractions (divide numerator and denominator by GCD). Distributing items equally. Finding the largest tile that fits a floor without cutting.
LCM: Finding when two events with different periods coincide (e.g. two buses with different intervals). Adding fractions (finding the common denominator). Scheduling problems.
LCM and GCD: What They Mean and the 2,300-Year-Old Shortcut
Built and verified by Andrius R. · Updated June 2026
The greatest common divisor (GCD) is the largest number that divides evenly into all of yours; the least common multiple (LCM) is the smallest number they all divide into. One shrinks problems down, the other finds where cycles meet — and a single ancient algorithm computes both.
Euclid's algorithm, step by step
Replace the larger number with the remainder of dividing it by the smaller; repeat until the remainder is 0:
48 ÷ 36 = 1 remainder 12 → now find GCD(36, 12)
36 ÷ 12 = 3 remainder 0 → done. GCD = 12.
Two steps instead of listing every divisor of both numbers. Described by Euclid around 300 BC, it's among the oldest algorithms still in daily use — your computer runs it constantly inside cryptographic code. Why it works: any number dividing both 48 and 36 must also divide their difference (and remainder), so the answer survives each shrinking step.
The bridge between them
For two numbers, LCM × GCD = the product of the numbers. So LCM(48, 36) = 48 × 36 ÷ 12 = 144 — no separate algorithm needed. (For three or more numbers this shortcut doesn't hold directly; compute pairwise instead, e.g. LCM(a, b, c) = LCM(LCM(a, b), c) — or let the calculator above do it.)
Where each one shows up in real life
| Problem | Tool | Example |
|---|---|---|
| Simplifying fractions & ratios | GCD | 36/48 → divide by 12 → 3/4 |
| Adding fractions | LCM | 1/12 + 1/18 → common denominator LCM(12,18) = 36 |
| Repeating schedules | LCM | Buses every 12 and 18 min that leave together align again after 36 min |
| Cutting/packing evenly | GCD | Largest equal pieces from 48 m and 36 m rolls: 12 m |
| Gear & rotation cycles | LCM | Two gears with 48 and 36 teeth realign after 144 tooth-engagements |
The prime-factor view (why the Venn diagram works)
Factor the numbers and the two concepts become visual: 48 = 2⁴ × 3 and 36 = 2² × 3². The GCD takes the lowest power of each shared prime (2² × 3 = 12); the LCM takes the highest power of every prime that appears (2⁴ × 3² = 144). The overlap region of the Venn diagram above is the GCD; the whole diagram is the LCM. For the factoring step itself, see the prime factorization calculator.
Three facts that resolve common confusions
- GCD ≤ the smallest input, LCM ≥ the largest. If your "GCD" came out bigger than one of the numbers, something's reversed.
- Coprime numbers (GCD = 1, like 8 and 15) have LCM equal to their product — the worst case for common denominators.
- LCM is not just "multiply them." 12 × 18 = 216 is a common multiple, but the least one is 36 — using the product instead of the LCM makes fraction arithmetic needlessly ugly, which is most people's actual complaint about fractions.
// Key Relationship
For any two numbers a and b: LCM(a,b) × GCD(a,b) = a × b. This is a handy way to find LCM if you know the GCD.
// Fractions
To add fractions, use the LCM of the denominators as the common denominator. The GCD of the numerator and denominator simplifies fractions.
// Co-prime Numbers
If GCD(a,b) = 1, the numbers are "co-prime" (relatively prime). Their LCM equals their product: LCM = a × b.
// Euclidean Algorithm
The Euclidean algorithm is one of the oldest known algorithms. It finds the GCD by repeatedly dividing — far faster than prime factorization for large numbers.