GCD & LCM Calculator
Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of multiple numbers.
Understanding GCD and LCM
The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are fundamental concepts in number theory and mathematics. They have numerous practical applications in everyday life, from simplifying fractions to scheduling recurring events.
What is the Greatest Common Divisor (GCD)?
The Greatest Common Divisor, also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides each of the given numbers without leaving a remainder. For example, the GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly.
Methods to Find GCD
- Prime Factorization: Factor each number into primes, then multiply the common prime factors
- Euclidean Algorithm: Repeatedly apply division: GCD(a,b) = GCD(b, a mod b) until remainder is 0
- Listing Factors: List all factors of each number and find the largest common one
Euclidean Algorithm Example
Find GCD(48, 18):
- 48 = 18 × 2 + 12
- 18 = 12 × 1 + 6
- 12 = 6 × 2 + 0
- GCD = 6
What is the Least Common Multiple (LCM)?
The Least Common Multiple is the smallest positive integer that is divisible by each of the given 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.
Relationship Between GCD and LCM
For any two positive integers a and b:
This means: LCM(a, b) = (a × b) / GCD(a, b)
Practical Applications
| Application | Uses GCD | Uses LCM |
|---|---|---|
| Simplifying Fractions | Divide numerator and denominator by GCD | - |
| Adding Fractions | - | Find common denominator using LCM |
| Scheduling Events | - | Find when events coincide (LCM of periods) |
| Tile Flooring | Find largest square tile that fits evenly | - |
| Gear Ratios | Simplify gear ratios | - |
| Music Theory | - | Find when rhythmic patterns align |
GCD and LCM for Multiple Numbers
To find the GCD or LCM of more than two numbers, you can apply the operation pairwise:
- GCD(a, b, c) = GCD(GCD(a, b), c)
- LCM(a, b, c) = LCM(LCM(a, b), c)
Special Cases
- Coprime Numbers: If GCD(a, b) = 1, the numbers are called coprime or relatively prime
- One Number Divides Another: If a divides b, then GCD(a, b) = a and LCM(a, b) = b
- GCD with 0: GCD(a, 0) = a (by convention)
Quick Reference
GCD (Greatest Common Divisor):
- Largest number that divides all inputs
- Always ≤ smallest input
- Used to simplify fractions
LCM (Least Common Multiple):
- Smallest number divisible by all inputs
- Always ≥ largest input
- Used for common denominators
Common GCD/LCM Pairs
| Numbers | GCD | LCM |
|---|---|---|
| 2, 3 | 1 | 6 |
| 4, 6 | 2 | 12 |
| 6, 8 | 2 | 24 |
| 12, 18 | 6 | 36 |
| 15, 20 | 5 | 60 |