🔢 GCD & LCM Calculator
Calculate Greatest Common Divisor and Least Common Multiple
📊 Enter Numbers
📊 Your Results
Greatest Common Divisor (GCD)
Least Common Multiple (LCM)
📝 Calculation Steps
📚 Understanding GCD and LCM
What is GCD (Greatest Common Divisor)?
The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides both 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.
What is LCM (Least Common Multiple)?
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by both numbers. For example, the LCM of 12 and 18 is 36, because 36 is the smallest number that both 12 and 18 divide into evenly.
How to Calculate GCD
The most efficient method to calculate GCD is the Euclidean Algorithm:
- Step 1: Divide the larger number by the smaller number
- Step 2: Replace the larger number with the smaller number
- Step 3: Replace the smaller number with the remainder from step 1
- Step 4: Repeat until the remainder is 0
- Step 5: The last non-zero remainder is the GCD
How to Calculate LCM
The LCM can be calculated using the relationship with GCD:
LCM(a, b) = (a × b) / GCD(a, b)
This formula works because the product of two numbers equals the product of their GCD and LCM.
Real-World Applications
- Scheduling: Finding when two events will occur simultaneously (LCM)
- Fractions: Simplifying fractions to lowest terms (GCD)
- Tile Patterns: Determining tile sizes that fit perfectly (GCD)
- Music: Finding when two rhythms align (LCM)
- Gear Ratios: Calculating gear teeth for mechanical systems
- Cryptography: Used in various encryption algorithms
Properties of GCD and LCM
- GCD(a, b) × LCM(a, b) = a × b - Fundamental relationship
- GCD(a, b) ≤ min(a, b) - GCD is never larger than the smaller number
- LCM(a, b) ≥ max(a, b) - LCM is never smaller than the larger number
- If GCD(a, b) = 1 - The numbers are coprime (relatively prime)
- GCD(a, 0) = a - Any number's GCD with 0 is itself
- LCM(a, 1) = a - Any number's LCM with 1 is itself
Frequently Asked Questions
What's the difference between GCD and LCM?
GCD is the largest number that divides both numbers evenly, while LCM is the smallest number that both numbers divide into evenly. GCD is always less than or equal to the smaller number, while LCM is always greater than or equal to the larger number.
Can GCD and LCM be calculated for more than two numbers?
Yes! For multiple numbers, calculate GCD or LCM pairwise. For example, GCD(a, b, c) = GCD(GCD(a, b), c). The same applies to LCM. This calculator focuses on two numbers for simplicity.
What are coprime numbers?
Two numbers are coprime (or relatively prime) if their GCD is 1. For example, 8 and 15 are coprime because GCD(8, 15) = 1. Coprime numbers have no common factors other than 1.
How is the Euclidean Algorithm efficient?
The Euclidean Algorithm is very efficient because it reduces the problem size rapidly with each step. It has a time complexity of O(log min(a, b)), making it much faster than checking all possible divisors, especially for large numbers.
Why is LCM(a, b) = (a × b) / GCD(a, b)?
This formula works because the product of two numbers contains all their prime factors. The GCD contains the common factors, so dividing by GCD removes the duplicate factors, leaving only the factors needed for the LCM.
What happens if one number is a multiple of the other?
If one number is a multiple of the other (e.g., 6 and 18), then the GCD is the smaller number (6) and the LCM is the larger number (18). This is because the smaller number divides the larger one perfectly.