GCD & LCM Calculator
Greatest Common Divisor & Least Multiple
GCD (HCF)
0
LCM
0
What is the Greatest Common Divisor (GCD)?
The GCD (also known as the Greatest Common Factor or HCF) is the largest positive integer that divides two or more numbers without leaving a remainder.
Example: Take the numbers 12 and 18.
- Factors of 12: 1, 2, 3, 4, 6, 12
- Factors of 18: 1, 2, 3, 6, 9, 18
The largest number that appears in both lists is 6. Therefore, the GCD is 6.
What is the Least Common Multiple (LCM)?
The LCM is the smallest positive integer that is divisible by both numbers.
Example: Take 4 and 5.
- Multiples of 4: 4, 8, 12, 16, 20, 24...
- Multiples of 5: 5, 10, 15, 20, 25...
The first number to appear in both lists is 20. Therefore, the LCM is 20.
How to Find GCD: The Prime Factorization Method
For small numbers, you can just list the factors. For large numbers (like 120 and 150), you use Prime Factorization.
- Break each number down into prime numbers.
- 120 = 2 ร 2 ร 2 ร 3 ร 5
- 150 = 2 ร 3 ร 5 ร 5
- Find the common primes: 2, 3, and 5.
- Multiply them: 2 ร 3 ร 5 = 30. The GCD is 30.
Our calculator does this automatically and shows you the breakdown!
Real World Applications
Why do we learn this in school? It solves efficiency problems.
The Tiling Problem (GCD):
You have a floor that is 240cm by 300cm. You want to cover it with square tiles of the largest possible size without cutting any tiles.
Calculate GCD(240, 300) = 60.
Answer: You should buy 60cm x 60cm tiles.
You have a floor that is 240cm by 300cm. You want to cover it with square tiles of the largest possible size without cutting any tiles.
Calculate GCD(240, 300) = 60.
Answer: You should buy 60cm x 60cm tiles.
The Scheduling Problem (LCM):
Bus A leaves every 12 minutes. Bus B leaves every 15 minutes. They just left together. When will they leave at the same time again?
Calculate LCM(12, 15) = 60.
Answer: They will sync up every 60 minutes.
Bus A leaves every 12 minutes. Bus B leaves every 15 minutes. They just left together. When will they leave at the same time again?
Calculate LCM(12, 15) = 60.
Answer: They will sync up every 60 minutes.