GCD & LCM Calculator
Calculate GCD and LCM of two or more numbers using the Euclidean algorithm.
What are GCD and LCM?
The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers without leaving a remainder. It represents the greatest shared factor between numbers and is essential for simplifying fractions, solving Diophantine equations, and finding common divisors.
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by each of the given numbers. LCM is useful when working with fractions (finding common denominators), scheduling recurring events, or solving problems involving cycles and intervals.
For two numbers a and b, GCD and LCM are related by the fundamental formula: LCM(a,b) = |a × b| / GCD(a,b). This relationship holds because the product of two numbers equals the product of their GCD and LCM. This calculator uses the Euclidean algorithm to compute GCD efficiently, then derives LCM from this formula when handling multiple numbers.
Key Properties
- Euclidean algorithm — An efficient method to compute GCD by repeated division with remainder.
- Associative for multiple numbers — GCD(a,b,c) = GCD(GCD(a,b), c), same for LCM.
- Coprime numbers — If GCD(a,b)=1, the numbers are coprime (relatively prime).
- GCD is a divisor — GCD divides every linear combination of the input numbers.
- LCM is a multiple — Every input number divides the LCM.
- Positive integers only — Both GCD and LCM are defined for positive integers.
How to Use
- Enter numbers — Type two or more positive integers separated by commas or spaces.
- Verify input — Ensure all numbers are positive integers (decimals and negative numbers are not valid).
- Calculate — Click Calculate to find GCD and LCM using the Euclidean algorithm.
- Review results — See the computed GCD and LCM values clearly displayed.
- View steps — See the step-by-step Euclidean algorithm showing the division process for transparency.
Common GCD and LCM Examples
| Numbers | GCD | LCM | Notes |
|---|---|---|---|
| 12, 18 | 6 | 36 | 6×12=72, 6×18=108 |
| 12, 18, 24 | 6 | 72 | Common divisor across all three |
| 8, 12 | 4 | 24 | Simplify 8/12 to 2/3 using GCD 4 |
| 15, 20 | 5 | 60 | Coprime factors 3 and 4 |
| 7, 13 | 1 | 91 | Coprime primes |
| 24, 36, 48 | 12 | 144 | Useful for common denominators |
| 6, 10, 15 | 1 | 30 | Coprime in pairs? GCD of all is 1 |
Worked Examples
- GCD of 48 and 18 (Euclidean) — 48 ÷ 18 = 2 remainder 12. 18 ÷ 12 = 1 remainder 6. 12 ÷ 6 = 2 remainder 0. GCD = 6.
- LCM of 48 and 18 — (48 × 18) / 6 = 864 / 6 = 144.
- GCD of 12, 18, 24 — GCD(12,18)=6, then GCD(6,24)=6.
- LCM of 12, 18, 24 — LCM(12,18)=36, then LCM(36,24)=72.
- Simplifying fractions — 36/60 ÷ GCD(36,60)=12 → 3/5.
- Common denominator — 1/4 + 1/6 = 3/12 + 2/12 = 5/12 using LCM(4,6)=12.
Tips and Common Mistakes
- At least two numbers — GCD and LCM require two or more numbers for meaningful results.
- Positive integers only — GCD and LCM are conventionally defined for positive integers; signs are usually ignored.
- Zero is special — GCD with zero: GCD(x,0)=|x|. Most calculators expect positive integers > 0.
- Use Euclidean for efficiency — The Euclidean algorithm is much faster than prime factorization for large numbers.
- Relation formula — For multiple numbers, you cannot just multiply and divide by a single GCD; compute stepwise.
- LCM can be large — LCM grows quickly; results can be much larger than individual inputs.
Common Use Cases
GCD and LCM appear in many real-world mathematical and practical scenarios:
- Fraction simplification — Divide numerator and denominator by their GCD to get simplest form.
- Adding/subtracting fractions — Find LCM of denominators as the common denominator.
- Scheduling and timing — LCM helps determine when events with different cycles repeat together.
- Cryptography — GCD is central to algorithms like RSA and modular arithmetic.
- Ratio and scaling — GCD reduces ratios to their simplest integer form.
- Problem solving — Useful in tiling, packaging, and arranging items into equal groups.
Frequently Asked Questions
What is GCD?
The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is the largest positive integer that divides all given numbers without a remainder. It is used to find common factors and simplify fractions.
What is LCM?
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by all given numbers. For two numbers, LCM(a, b) = |a × b| / GCD(a, b).
How does the Euclidean algorithm work?
The Euclidean algorithm repeatedly divides the larger number by the smaller and replaces the larger with the remainder until the remainder is zero. The last non-zero divisor is the GCD. It is efficient and one of the oldest algorithms still in common use.
What is the difference between GCD and HCF?
GCD (Greatest Common Divisor) and HCF (Highest Common Factor) mean the same thing. Both refer to the largest number that divides two or more numbers without a remainder. The terms are used interchangeably in mathematics.
Can GCD and LCM be calculated for more than two numbers?
Yes. For multiple numbers, compute stepwise: GCD(a,b,c) = GCD(GCD(a,b), c) and LCM(a,b,c) = LCM(LCM(a,b), c). This calculator supports two or more numbers.
What does it mean if GCD is 1?
If GCD of two numbers is 1, they are coprime (or relatively prime). This means they have no common positive divisor other than 1, which is important in number theory and cryptography.
How is LCM related to fractions?
LCM of denominators gives the least common denominator (LCD) when adding or subtracting fractions. This allows you to combine fractions with different denominators into a single expression.
What are the limitations for large numbers?
The calculator computes exact integer results using the Euclidean algorithm. For extremely large integers, the steps are still mathematically valid, though display formatting depends on the number size.