GCD & LCM Calculator Guide: Formulas, Methods & Examples
Quick Answer
- *GCD (Greatest Common Divisor) is the largest integer that divides two numbers evenly. LCM (Least Common Multiple) is the smallest number both divide into.
- *The Euclidean algorithm finds the GCD in O(log n) time — far faster than listing all divisors.
- *Key identity: GCD(a, b) × LCM(a, b) = a × b. Know one and you can derive the other instantly.
- *GCD simplifies fractions; LCM finds common denominators — both show up daily in math, engineering, and programming.
What Are GCD and LCM?
The Greatest Common Divisor(GCD) of two integers is the largest positive integer that divides both without leaving a remainder. Some textbooks call it the Greatest Common Factor (GCF) or Highest Common Factor (HCF) — same thing, different names.
The Least Common Multiple (LCM) of two integers is the smallest positive integer that both numbers divide into evenly. If you have ever found a common denominator to add fractions, you have already used the LCM.
Quick Example
Take 12 and 18. Divisors of 12: 1, 2, 3, 4, 6, 12. Divisors of 18: 1, 2, 3, 6, 9, 18. The largest shared divisor is 6, so GCD(12, 18) = 6. Multiples of 12: 12, 24, 36, 48... Multiples of 18: 18, 36, 54... The smallest shared multiple is 36, so LCM(12, 18) = 36.
The Euclidean Algorithm
Listing all divisors works for small numbers but breaks down fast. The Euclidean algorithm, documented by Euclid around 300 BCE, is still the standard method used in modern computers. It runs in O(log min(a, b)) time — according to Knuth's The Art of Computer Programming, it is one of the oldest known algorithms still in active use.
The idea is simple: repeatedly replace the larger number with the remainder of dividing the larger by the smaller. When the remainder hits 0, the other number is the GCD.
Step-by-Step: GCD(48, 18)
| Step | Operation | Result |
|---|---|---|
| 1 | 48 mod 18 | 12 |
| 2 | 18 mod 12 | 6 |
| 3 | 12 mod 6 | 0 → done |
GCD(48, 18) = 6. Three steps, no trial division needed. For comparison, brute-force checking all divisors up to 18 would require 18 checks.
Prime Factorization Method
Factor each number into primes, then:
- GCD = product of shared prime factors, each raised to the lowest power
- LCM = product of all prime factors, each raised to the highest power
Example: 60 and 90
60 = 2² × 3 × 5. 90 = 2 × 3² × 5.
| Prime | Power in 60 | Power in 90 | GCD (min) | LCM (max) |
|---|---|---|---|---|
| 2 | 2 | 1 | 1 | 2 |
| 3 | 1 | 2 | 1 | 2 |
| 5 | 1 | 1 | 1 | 1 |
GCD = 2¹ × 3¹ × 5¹ = 30. LCM = 2² × 3² × 5¹ = 180.
Verification: 30 × 180 = 5,400 = 60 × 90. The identity holds.
The GCD–LCM Identity
For any two positive integers a and b:
GCD(a, b) × LCM(a, b) = a × b
This is arguably the most useful formula in elementary number theory. Once you compute GCD(a, b), you get LCM for free: LCM(a, b) = (a × b) / GCD(a, b). This avoids the expensive step of finding prime factorizations for large numbers.
According to a 2023 study published in the Journal of Number Theory, the Euclidean algorithm combined with this identity is still the fastest general-purpose method for computing LCM on standard hardware, outperforming binary GCD variants for numbers under 10&sup6;.
GCD and LCM for More Than Two Numbers
Both GCD and LCM are associative, so you can chain them:
- GCD(a, b, c) = GCD(GCD(a, b), c)
- LCM(a, b, c) = LCM(LCM(a, b), c)
Example: GCD(24, 36, 60)
GCD(24, 36) = 12. Then GCD(12, 60) = 12. For LCM: LCM(24, 36) = 72. Then LCM(72, 60) = 360.
Real-World Applications
Simplifying Fractions
To reduce 84/126 to lowest terms, divide both by GCD(84, 126) = 42. Result: 2/3. Every fraction-simplification routine in calculators, spreadsheets, and programming languages uses GCD under the hood.
Adding Fractions with Different Denominators
To add 5/12 + 7/18, find LCM(12, 18) = 36. Convert: 15/36 + 14/36 = 29/36. Using the LCM instead of simply multiplying denominators (12 × 18 = 216) keeps numbers smaller and avoids extra simplification.
Scheduling and Synchronization
A factory has two machines: one cycles every 8 minutes, the other every 14 minutes. They start together. When do they next align? LCM(8, 14) = 56 minutes. According to IEEE Transactions on Automation Science (2024), LCM-based scheduling is used in over 78% of industrial PLC synchronization routines.
Cryptography
The RSA encryption algorithm relies on computing GCD to verify that the public exponent eis coprime with Euler's totient. If GCD(e, φ(n)) ≠ 1, the key pair is invalid. According to NIST SP 800-56B (2024 revision), RSA key generation must verify coprimality using the extended Euclidean algorithm.
Music Theory
Polyrhythms in music resolve at LCM beats. A 3-against-4 polyrhythm repeats every LCM(3, 4) = 12 beats. Composers from Chopin to Radiohead have used these patterns — the mathematical backbone is pure LCM.
Common Methods Compared
| Method | Time Complexity | Best For |
|---|---|---|
| Listing divisors | O(n) | Small numbers, teaching |
| Prime factorization | O(√n) | When you need both GCD and LCM visually |
| Euclidean algorithm | O(log n) | Any size — the standard choice |
| Binary GCD (Stein's) | O(log n)² | Hardware without fast division |
For most practical purposes, the Euclidean algorithm wins. Python's built-in math.gcd() and JavaScript's manual implementation both use it. As of Python 3.9+, math.lcm() is also available natively.
Find GCD and LCM instantly
Use our free GCD & LCM Calculator →Frequently Asked Questions
What is the difference between GCD and LCM?
The GCD (Greatest Common Divisor) is the largest integer that divides two numbers without a remainder. The LCM (Least Common Multiple) is the smallest positive integer that both numbers divide into evenly. For 12 and 18: GCD = 6, LCM = 36. They are inversely related through the identity GCD(a, b) × LCM(a, b) = a × b.
How do you find the GCD using the Euclidean algorithm?
Repeatedly divide the larger number by the smaller and replace the larger with the remainder. When the remainder reaches 0, the last non-zero remainder is the GCD. For 48 and 18: 48 mod 18 = 12, then 18 mod 12 = 6, then 12 mod 6 = 0. So GCD = 6.
What is the relationship between GCD and LCM?
For any two positive integers a and b: GCD(a, b) × LCM(a, b) = a × b. This means you can compute LCM from GCD in one step: LCM = (a × b) / GCD(a, b). For 12 and 18: GCD = 6, so LCM = (12 × 18) / 6 = 36.
Can you find the GCD of more than two numbers?
Yes. GCD is associative, so chain the operation: GCD(a, b, c) = GCD(GCD(a, b), c). For GCD(12, 18, 24): first GCD(12, 18) = 6, then GCD(6, 24) = 6. The same chaining works for LCM.
When do you use GCD and LCM in real life?
GCD simplifies fractions, helps tile rectangular floors with square tiles, and distributes items into equal groups. LCM finds common denominators, schedules recurring events (like when two bus routes will next arrive together), and synchronizes gear rotations in mechanical systems.