LCM and GCD Calculator — Find Multiples and Divisors
Free online LCM and GCD calculator. Compute the Least Common Multiple and Greatest Common Divisor of two or more numbers.
Try the free calculator
Put these formulas into practice with our instant, step-by-step LCM & GCD Calculator.
TL;DR
The Greatest Common Divisor (GCD) is the largest number that divides two or more numbers without a remainder. The Least Common Multiple (LCM) is the smallest number divisible by both. They are related by the formula: LCM(a,b) = (a × b) / GCD(a,b). The Euclidean algorithm efficiently computes the GCD. Essential for simplifying fractions, finding common denominators, scheduling problems, and cryptography.
Free — no sign-up required
The Greatest Common Divisor (GCD) is the largest positive integer that divides two or more numbers without leaving a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is divisible by two or more numbers. An LCM and GCD calculator computes both values simultaneously, providing essential tools for simplifying fractions, solving Diophantine equations, scheduling problems, and working with periodic phenomena. These concepts are foundational in number theory and have practical applications across mathematics, computer science, and engineering.
What Is GCD?
The Greatest Common Divisor (GCD), also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest number that divides two or more integers without leaving a remainder. For example, the GCD of 24 and 36 is 12, because 12 is the largest number that divides both 24 and 36 evenly.
The GCD is useful for reducing fractions to their simplest form. To simplify 12/18, find the GCD of 12 and 18 (which is 6), then divide both numbers by it to get 2/3. Simplified fractions are easier to compare, add, and work with in calculations. The GCD is also used in solving Diophantine equations and in cryptography algorithms like RSA.
Quick Definition
The GCD of two or more integers is the largest positive integer that divides each of the integers without a remainder. If GCD(a,b) = 1, the numbers are said to be coprime or relatively prime.
What Is LCM?
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by two or more numbers. For example, the LCM of 4 and 6 is 12, because 12 is the smallest number that both 4 and 6 divide into evenly. The LCM is useful for finding common denominators when adding or subtracting fractions.
To add 1/3 and 1/4, find the LCM of 3 and 4 (which is 12) and convert both fractions: 1/3 = 4/12 and 1/4 = 3/12. Now you can add them: 4/12 + 3/12 = 7/12. The LCM is also essential in scheduling problems — if two events occur every 4 and 6 days respectively, they will both occur on the same day every 12 days.
The GCD-LCM Relationship
The GCD and LCM are complementary concepts connected by a fundamental relationship:
This means if you know the GCD of two numbers, you can find their LCM by dividing the product of the numbers by the GCD. For example, if GCD(12, 18) = 6, then LCM(12, 18) = (12 × 18) / 6 = 216 / 6 = 36. This relationship allows a calculator to compute both values from a single computation.
| Numbers | GCD | LCM | Verification |
|---|---|---|---|
| 12, 18 | 6 | 36 | 6 × 36 = 216 = 12 × 18 ✓ |
| 8, 12 | 4 | 24 | 4 × 24 = 96 = 8 × 12 ✓ |
| 15, 25 | 5 | 75 | 5 × 75 = 375 = 15 × 25 ✓ |
The Euclidean Algorithm
The Euclidean algorithm is the most efficient method for computing the GCD. It works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero. The last non-zero remainder is the GCD. This algorithm dates back to around 300 BCE and remains one of the oldest algorithms still in common use.
Step-by-Step: GCD of 48 and 18
- 48 ÷ 18 = 2 remainder 12
- 18 ÷ 12 = 1 remainder 6
- 12 ÷ 6 = 2 remainder 0
- Last non-zero remainder = 6 → GCD(48, 18) = 6
This algorithm runs in logarithmic time, O(log(min(a,b))), making it practical even for very large numbers. It is used in computer science for computing modular inverses, in cryptography for key generation, and in simplifying fractions programmatically.
Prime Factorization Method
Another way to find the GCD and LCM is through prime factorization. Break each number into its prime factors, then:
- GCD: Take the lowest power of each common prime factor.
- LCM: Take the highest power of each prime factor present in any number.
For example, 12 = 2² × 3 and 18 = 2 × 3². The GCD is 2¹ × 3¹ = 6. The LCM is 2² × 3² = 36. This method is more intuitive for small numbers and helps visualize why the GCD-LCM relationship works.
Worked Examples
Example 1: GCD and LCM of 24 and 36
Prime factors: 24 = 2³ × 3, 36 = 2² × 3²
GCD = 2² × 3 = 12
LCM = 2³ × 3² = 72
Verify: 12 × 72 = 864 = 24 × 36 ✓
Example 2: Simplifying 48/18
GCD(48, 18) = 6. Divide both by 6: 48/6 = 8, 18/6 = 3
Result: 8/3 (simplified fraction)
Example 3: Adding 1/6 + 1/8
LCM(6, 8) = 24. Convert: 1/6 = 4/24, 1/8 = 3/24
Result: 4/24 + 3/24 = 7/24
Real-World Applications
GCD and LCM calculations appear in many practical contexts. In scheduling, if two machines need maintenance every 6 and 8 hours respectively, they will both need maintenance simultaneously every LCM(6, 8) = 24 hours. In gear ratio calculations, the GCD determines the simplest integer ratio for gear teeth.
In computer science, the GCD is used in algorithms for computing modular inverses (essential for RSA cryptography) and in hash table sizing (choosing table sizes that are coprime to the hash function). In music theory, the GCD of two rhythmic patterns determines their combined cycle length. Understanding these concepts gives you tools to solve problems across mathematics, engineering, and computer science.
Frequently Asked Questions
What is the GCD of two prime numbers?
If two numbers are both prime and different, their GCD is 1 (they are coprime). If they are the same prime number, the GCD is that number.
What is the LCM of two prime numbers?
If two numbers are both prime and different, their LCM is their product. For example, LCM(3, 7) = 21.
What does GCD = 1 mean?
It means the numbers are coprime (or relatively prime) — they share no common factors other than 1. For example, GCD(8, 15) = 1.
Can GCD be larger than both numbers?
No, the GCD cannot be larger than the smallest number in the set. The GCD is always less than or equal to the smallest number.
How do I find GCD for more than two numbers?
Compute the GCD of the first two numbers, then compute the GCD of that result with the third number, and so on. The same iterative approach works for any number of inputs.
What is the Euclidean algorithm?
The Euclidean algorithm computes the GCD by repeatedly dividing the larger number by the smaller and replacing the larger with the remainder, until the remainder is zero. The last non-zero remainder is the GCD.
How are GCD and LCM related?
The product of the GCD and LCM of two numbers equals the product of the numbers: GCD(a,b) × LCM(a,b) = a × b.
Where is GCD used in real life?
GCD is used in simplifying fractions, scheduling problems, gear ratios, cryptography (RSA), hash table sizing, and finding coprime numbers for mathematical proofs.