GCD & LCM Calculator — Greatest Common Divisor and Least Common Multiple
The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are two of the most useful concepts in arithmetic. GCD tells you the largest number that divides evenly into both integers — handy for simplifying fractions or splitting things into equal groups. LCM tells you the smallest number that is a multiple of both — essential for adding fractions with different denominators or synchronizing repeating events. This calculator uses the classic Euclidean algorithm, which runs in O(log min(a,b)) steps and is exact for any pair of positive integers.
To find GCD and LCM of two integers: (1) Apply the Euclidean algorithm — repeatedly replace (a, b) with (b, a mod b) until b = 0; the last non-zero remainder is the GCD. (2) LCM(a, b) = (a × b) ÷ GCD(a, b). Example: GCD(48, 36) = 12, LCM(48, 36) = 144. Key identity: GCD × LCM = a × b always holds.
When to use this calculator
- Simplifying fractions: divide numerator and denominator by their GCD to reach lowest terms (e.g., 36/48 → 3/4 because GCD = 12).
- Adding unlike fractions: find LCM of the denominators to get the least common denominator (e.g., 1/4 + 1/6 needs LCM(4,6) = 12).
- Scheduling: if event A repeats every 8 days and event B every 12 days, LCM(8,12) = 24 tells you they coincide every 24 days.
- Gear ratios and tiling: GCD reveals the largest tile size that fits a floor evenly, or the highest gear reduction with no remainder.
Worked example: a = 48, b = 36
- Apply Euclidean algorithm: GCD(48, 36)
- Step 1 — 48 = 1 × 36 + 12 → GCD(36, 12)
- Step 2 — 36 = 3 × 12 + 0 → remainder is 0, so GCD = 12
- LCM = (48 × 36) / 12 = 1728 / 12 = 144
- Check: GCD × LCM = 12 × 144 = 1728 = 48 × 36 ✓
How it works
2 min readWhat GCD and LCM mean
The Greatest Common Divisor (also called Greatest Common Factor, GCF) of two positive integers a and b is the largest positive integer d such that d | a and d | b (d divides both without remainder). For example, the divisors of 48 are {1, 2, 3, 4, 6, 8, 12, 16, 24, 48} and the divisors of 36 are {1, 2, 3, 4, 6, 9, 12, 18, 36}. The largest value in both sets is 12, so GCD(48, 36) = 12.
The Least Common Multiple is the smallest positive integer that is divisible by both a and b. Multiples of 48: 48, 96, 144 … Multiples of 36: 36, 72, 108, 144 … The first they share is 144, so LCM(48, 36) = 144.
How it's calculated
Euclidean algorithm for GCD
The algorithm is based on the identity: GCD(a, b) = GCD(b, a mod b). It repeats until the remainder is 0:
function gcd(a, b):
while b ≠ 0:
(a, b) = (b, a mod b)
return aExample — GCD(48, 36):
1. GCD(48, 36) → GCD(36, 48 mod 36) = GCD(36, 12)
2. GCD(36, 12) → GCD(12, 36 mod 12) = GCD(12, 0)
3. b = 0, so GCD = 12
LCM from GCD
Once GCD is known, LCM follows from the fundamental identity:
LCM(a, b) = (a × b) / GCD(a, b)This avoids computing LCM from scratch and is always exact for integers. In the example: LCM = (48 × 36) / 12 = 144.
Coprime numbers
If GCD(a, b) = 1, the two numbers are called coprime (or relatively prime). Their LCM equals their product (e.g., GCD(8, 15) = 1, LCM = 120). This calculator detects this case and flags it in the summary.
Quick-reference table: GCD and LCM for common pairs
| a | b | GCD | LCM | Simplified ratio a/b |
|---|---|---|---|---|
| 6 | 9 | 3 | 18 | 2/3 |
| 8 | 12 | 4 | 24 | 2/3 |
| 12 | 18 | 6 | 36 | 2/3 |
| 15 | 20 | 5 | 60 | 3/4 |
| 24 | 36 | 12 | 72 | 2/3 |
| 36 | 48 | 12 | 144 | 3/4 |
| 48 | 60 | 12 | 240 | 4/5 |
| 100 | 75 | 25 | 300 | 4/3 |
| 360 | 420 | 60 | 2520 | 6/7 |
| 8 | 15 | 1 | 120 | coprime |
| 17 | 13 | 1 | 221 | coprime |
> When GCD(a, b) = 1, the numbers are coprime — they share no prime factors, and LCM = a × b.
Practical formulas
| Goal | Formula |
|---|---|
| Simplify fraction a/b | Divide numerator and denominator by GCD(a, b) |
| Least common denominator for 1/a + 1/b | LCM(a, b) |
| Next time two cycles sync | LCM(period₁, period₂) |
| Tile a W×H rectangle with largest square tiles | GCD(W, H) = tile side length |
Frequently asked questions
What is the difference between GCD and GCF?
They are the same thing — Greatest Common Divisor (GCD) and Greatest Common Factor (GCF) are two names for the same concept. Some textbooks (especially US K-12) prefer GCF; number theory literature typically uses GCD. Both equal the largest positive integer that divides both numbers without remainder.
How does the Euclidean algorithm find GCD step by step?
It repeatedly replaces the pair (a, b) with (b, a mod b) until b reaches 0. The last non-zero value of a is the GCD. For GCD(48, 36): 48 mod 36 = 12 → pair becomes (36, 12). 36 mod 12 = 0 → pair becomes (12, 0). Since b = 0, GCD = 12. This is far faster than listing all divisors, especially for large numbers.
Why does LCM(a, b) = (a × b) / GCD(a, b)?
This follows from the prime factorization of both numbers. If you decompose a and b into primes, GCD takes the minimum exponent for each prime while LCM takes the maximum. Their product covers each prime exactly once at min + max = the sum, which equals the product a × b. Hence GCD × LCM = a × b, and LCM = (a × b) / GCD. Example: a = 12 = 2² × 3, b = 18 = 2 × 3². GCD = 2¹ × 3¹ = 6. LCM = 2² × 3² = 36. Check: 6 × 36 = 216 = 12 × 18 ✓
What does it mean when GCD equals 1?
The two numbers share no common factors other than 1, so they are called coprime (or relatively prime). Examples: GCD(8, 15) = 1, GCD(9, 25) = 1, GCD(11, 13) = 1. Their LCM equals their product. Coprimality is important in cryptography — RSA relies on choosing two large coprime numbers. Note that two numbers can be coprime even if neither is prime: 8 and 9 are coprime despite 8 = 2³ and 9 = 3².
How do I use GCD to simplify a fraction to lowest terms?
Divide both the numerator and denominator by their GCD. For 36/48: GCD(36, 48) = 12, so 36/12 = 3 and 48/12 = 4, giving 3/4 — the fully simplified form. If GCD = 1, the fraction is already in lowest terms (irreducible). For 84/120: GCD = 12, giving 7/10. Check: GCD(7, 10) = 1 ✓.
How do I use LCM to add fractions with different denominators?
Find LCM of the denominators — that is the least common denominator (LCD). For 1/4 + 1/6: LCM(4, 6) = 12, so rewrite as 3/12 + 2/12 = 5/12. Using LCM (not just any common multiple) keeps the numbers as small as possible and avoids unnecessary simplification afterward.
Can I find GCD and LCM for more than two numbers?
Yes, by chaining: GCD(a, b, c) = GCD(GCD(a, b), c). For example, GCD(12, 18, 30) = GCD(GCD(12,18), 30) = GCD(6, 30) = 6. The same applies to LCM: LCM(a, b, c) = LCM(LCM(a, b), c). For LCM(12, 18, 30): LCM(12, 18) = 36, then LCM(36, 30) = 180. You can repeat for any number of integers.
What happens if one of the numbers is 0 or negative?
By convention, GCD(a, 0) = a for any positive integer a, and GCD of negative numbers uses absolute values. This calculator requires both inputs to be positive non-zero integers for practical use. It automatically applies absolute value to inputs, so GCD(−48, 36) returns the same result as GCD(48, 36) = 12. Entering 0 returns an error message.
What real-world problems use LCM for scheduling?
If machine A needs maintenance every 8 hours and machine B every 12 hours, LCM(8, 12) = 24 means they both need maintenance at the same time every 24 hours — useful for planning a combined shutdown. Similarly, two traffic lights with cycles of 60 s and 90 s first synchronize again after LCM(60, 90) = 180 seconds. Music: a 3-beat and a 4-beat pattern align every LCM(3, 4) = 12 pulses.
How is the Euclidean algorithm related to RSA cryptography?
RSA key generation requires two steps that use Euclid: (1) checking that a number e is coprime to φ(n) — done via GCD(e, φ(n)) = 1; (2) computing the modular inverse of e modulo φ(n) using the Extended Euclidean Algorithm, which returns coefficients x, y such that ex + φ(n)y = 1. Without the Euclidean algorithm, modern public-key cryptography as used in HTTPS and banking would be computationally impractical.