GCD & LCM Calculator — Greatest Common Divisor & Least Common Multiple
Calculate the Greatest Common Divisor and Least Common Multiple of 2 or more numbers with step-by-step Euclidean algorithm display. All calculations happen locally — nothing leaves your browser.
How to Use the GCD & LCM Calculator
- Enter numbers — start with 2 numbers, or click "Add Number" for more.
- View results — see the GCD and LCM calculated instantly.
- Follow the steps — the Euclidean algorithm shows each division step.
- Check coprimality — see if the numbers share any common factors beyond 1.
- Verify the formula — confirm that GCD × LCM = a × b.
Why GCD and LCM Matter
The Greatest Common Divisor (GCD) is the largest number that divides two or more numbers evenly. The Least Common Multiple (LCM) is the smallest number that both divide into evenly.
These concepts are fundamental in fractions (simplifying, finding common denominators), cryptography, scheduling problems, and gear ratio calculations.
How It Works
The Euclidean algorithm finds the GCD by repeatedly applying the division algorithm. Given two numbers a and b (where a > b), divide a by b to get a remainder r. Then replace a with b and b with r. Repeat until the remainder is 0. The last non-zero remainder is the GCD.
For example, to find GCD(48, 18):
48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0
GCD = 6
The LCM is then calculated using the formula: LCM(a,b) = (a × b) / GCD(a,b). For the example above: LCM(48, 18) = (48 × 18) / 6 = 144.
Examples
Example 1: GCD(24, 36)
Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
Common factors: 1, 2, 3, 4, 6, 12
GCD = 12 · LCM = 72
Example 2: GCD(7, 13) — Coprime Numbers
7 and 13 are both prime and share no common factors other than 1.
GCD = 1 · LCM = 91
These numbers are coprime.
Example 3: GCD(100, 60)
100 = 60 × 1 + 40
60 = 40 × 1 + 20
40 = 20 × 2 + 0
GCD = 20 · LCM = 300
Mathematical Properties
- GCD × LCM = a × b — For any two positive integers, the product of their GCD and LCM equals the product of the numbers themselves.
- Commutativity: GCD(a, b) = GCD(b, a) and LCM(a, b) = LCM(b, a).
- Associativity: GCD(a, GCD(b, c)) = GCD(GCD(a, b), c). The same holds for LCM.
- Coprime numbers: Two numbers are coprime if and only if GCD(a, b) = 1. In this case, LCM(a, b) = a × b.
- Divisibility: GCD(a, b) always divides both a and b. Both a and b always divide LCM(a, b).
- Distributive property: GCD(a, LCM(b, c)) = LCM(GCD(a, b), GCD(a, c)).
- Scaling: GCD(k×a, k×b) = k × GCD(a, b) for any positive integer k.
Frequently Asked Questions
You can add as many numbers as needed. The GCD and LCM are computed iteratively across all entered numbers.
The Euclidean algorithm finds the GCD by repeatedly dividing the larger number by the smaller and taking the remainder, until the remainder is 0. The last non-zero remainder is the GCD.
Two numbers are coprime if their GCD is 1, meaning they share no common factors other than 1. For example, 8 and 15 are coprime (GCD = 1).
The GCD is the product of all common prime factors (with lowest exponent). The LCM is the product of all prime factors (with highest exponent). This method helps visualize why GCD and LCM are related.
Use Cases
Simplifying Fractions in Math Homework
Quickly find the GCD to reduce fractions to their simplest form, making math homework easier and faster.
Finding Common Denominators
Use LCM to find the least common denominator when adding or subtracting fractions with different denominators.
Scheduling Recurring Events
Calculate when two periodic events will coincide again using LCM, perfect for scheduling maintenance or meetings.
Gear Ratio Calculations
Determine optimal gear ratios for mechanical systems by calculating GCD and LCM of teeth counts on different gears.
Cryptographic Algorithm Sizing
Help size cryptographic parameters and understand number theory concepts used in RSA and other encryption algorithms.