GCD & LCM Calculator
Find the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two numbers simultaneously.
Quick Examples
Understanding GCD and LCM
Greatest Common Divisor (GCD)
The GCD of two or more integers is the largest positive integer that divides each of them without a remainder.
Least Common Multiple (LCM)
The LCM of two or more integers is the smallest positive integer that is divisible by each of them.
The Fundamental Relationship
Examples
| Numbers | GCD | LCM |
|---|---|---|
| 12, 18 | 6 | 36 |
| 24, 36 | 12 | 72 |
| 15, 25 | 5 | 75 |
| 8, 12 | 4 | 24 |
| 7, 11 | 1 | 77 |
The Euclidean Algorithm: Finding GCD Step by Step
The fastest reliable way to find a GCD by hand is the Euclidean algorithm, described by Euclid around 300 BCE and still the standard method today. It works by repeated division: divide the larger number by the smaller, keep the remainder, then repeat with the smaller number and that remainder. When a remainder of zero appears, the last non-zero remainder is the GCD.
Worked Example: GCD(48, 18)
| Step | Division | Remainder |
|---|---|---|
| 1 | 48 = 2 x 18 + 12 | 12 |
| 2 | 18 = 1 x 12 + 6 | 6 |
| 3 | 12 = 2 x 6 + 0 | 0 (stop) |
The last non-zero remainder is 6, so GCD(48, 18) = 6. Once the GCD is known, the LCM comes almost free: LCM(48, 18) = (48 x 18) / 6 = 864 / 6 = 144.
Why Euclid Beats Listing Factors
Listing all factors works for small numbers, but for large inputs it is slow. The Euclidean algorithm finishes in at most five times the number of digits of the smaller input (proved by Gabriel Lame in 1844), so even billion-scale inputs need only a few dozen division steps. This is the method the calculator above uses.
The Prime Factorization Method
Prime factorization shows why GCD and LCM work, even though it is slower than Euclid's algorithm for big numbers. Break each number into primes, then compare exponents.
Worked Example: 12 and 18
- 12 = 2 x 2 x 3
- 18 = 2 x 3 x 3
- GCD takes the lowest exponent of each shared prime: 2 x 3 = 6
- LCM takes the highest exponent of each prime: 4 x 9 = 36
GCD and LCM of More Than Two Numbers
Both operations chain left to right. Compute the first pair, then combine the result with the next number, and so on:
Worked Example: 24, 36, 60
- GCD(24, 36) = 12; then GCD(12, 60) = 12. So GCD(24, 36, 60) = 12.
- LCM(24, 36) = 72; then LCM(72, 60) = 360. So LCM(24, 36, 60) = 360.
- Check with the product test for the final pair: 72 x 60 = 4320 and 12 x 360 = 4320.
GCD vs LCM: When to Use Each
| GCD | LCM | |
|---|---|---|
| Asks | What is the largest piece I can divide everything into? | When will everything line up again? |
| Typical use | Simplifying fractions, splitting items into equal groups, largest square tile for a floor | Common denominators, scheduling repeating events, syncing cycles |
| Size | Always less than or equal to the smallest input | Always greater than or equal to the largest input |
| Example (12, 18) | 6 | 36 |
One always divides the other: GCD(a, b) is always a divisor of LCM(a, b). In the example, 36 / 6 = 6 exactly.
Real-World Applications
| Application | Uses | Example |
|---|---|---|
| Simplifying fractions | GCD | 24/36 simplifies to 2/3 by dividing both by GCD(24, 36) = 12 |
| Adding fractions | LCM | 1/15 + 1/25 needs a common denominator: LCM(15, 25) = 75 |
| Scheduling | LCM | Bus A runs every 12 minutes, bus B every 18 minutes; both leave together every LCM(12, 18) = 36 minutes |
| Tiling a floor | GCD | A 12 x 18 ft room is tiled with the largest square tiles that fit evenly: GCD(12, 18) = 6 ft |
| Cryptography | GCD | RSA key generation requires GCD(e, phi) = 1, a coprimality check |
| Gear ratios | GCD | Gears with 48 and 36 teeth simplify by GCD(48, 36) = 12 to a 4:3 ratio |
Special Cases and Properties
- Coprime numbers: when GCD = 1, the numbers share no factors other than 1. Example: 7 and 13 are coprime, so GCD(7, 13) = 1 and LCM(7, 13) = 7 x 13 = 91. Two consecutive integers are always coprime.
- One number divides the other: the GCD is the smaller number and the LCM is the larger. Example: GCD(6, 18) = 6 and LCM(6, 18) = 18.
- Equal numbers: GCD(n, n) = LCM(n, n) = n.
- Zero: GCD(0, n) = n, and by the standard convention LCM(0, n) = 0.
- Negative numbers: GCD and LCM are defined on absolute values, so GCD(-12, 18) = GCD(12, 18) = 6.
- Three names, one concept: GCD (greatest common divisor), GCF (greatest common factor, common in American textbooks), and HCF (highest common factor, common in British curricula) all mean the same thing.
Common Mistakes to Avoid
- Confusing the two: GCD splits things down (largest shared divisor); LCM builds things up (smallest shared multiple). If your "GCD" is larger than the smallest input, you computed the LCM by accident.
- Assuming LCM is always the product: the product a x b is the LCM only when the numbers are coprime (GCD = 1). For 12 and 18 the product is 216, but the LCM is 36.
- Listing multiples for large numbers: listing works for 4 and 6 but is impractical for 480 and 720 — use the Euclidean algorithm and the GCD identity instead.
- Forgetting the identity check: GCD x LCM must equal a x b. If it does not, one of the two results is wrong.
Quick Plausibility Check
Before trusting any GCD/LCM answer, run this 10-second check:
- Bounds: is the GCD less than or equal to the smallest input, and the LCM greater than or equal to the largest input?
- Divisibility: does the GCD divide the LCM evenly? (For 12 and 18: 36 / 6 = 6, no remainder.)
- Product test: does GCD x LCM equal a x b? (6 x 36 = 216 = 12 x 18.)
If all three pass, the answer is almost certainly right. Most wrong answers fail at least one of these checks.