GCD and LCM Calculator — Greatest Common Divisor & Least Common Multiple
Calculate GCD (greatest common divisor) and LCM (least common multiple) for two or more numbers. Includes Euclidean algorithm steps and fraction applications.
GCD and LCM are number theory fundamentals that show up in fraction arithmetic, scheduling problems, and cryptography. They sound similar — both involve common factors — but they answer completely different questions. The CalcHub GCD/LCM Calculator computes both and shows you the steps, which is useful when you need to understand the method, not just the answer.
Quick Definitions
GCD (Greatest Common Divisor) — also called HCF (Highest Common Factor) — is the largest number that divides evenly into all the numbers you give it. LCM (Least Common Multiple) is the smallest number that all your inputs divide evenly into.GCD(12, 18) = 6 — because 6 is the largest divisor both share.
LCM(12, 18) = 36 — because 36 is the smallest number both divide into.
How to Use It
- Enter two or more numbers (comma-separated for more than two).
- Select GCD, LCM, or both.
- Click Calculate. The result includes the intermediate factorization steps.
The Euclidean Algorithm (GCD)
This is the classic method — fast even for large numbers:
Example: GCD(252, 105)GCD(a, b) = GCD(b, a mod b), repeating until the remainder is 0.
- 252 = 2 × 105 + 42 → GCD(252, 105) = GCD(105, 42)
- 105 = 2 × 42 + 21 → GCD(105, 42) = GCD(42, 21)
- 42 = 2 × 21 + 0 → GCD = 21
Prime Factorization Method
An alternative that's more intuitive:
| Number | Prime Factors |
|---|---|
| 60 | 2² × 3 × 5 |
| 84 | 2² × 3 × 7 |
The relationship between them is always:
GCD(a, b) × LCM(a, b) = a × b
So: 12 × 420 = 60 × 84 = 5,040. This is a useful check.
Where These Show Up
Fraction arithmetic: To add 5/12 + 7/18, you need the LCM of 12 and 18 (= 36) as the common denominator. To simplify 18/24, you divide both by GCD(18, 24) = 6, giving 3/4. Scheduling: Two events repeat every 12 days and 18 days. When do they next coincide? LCM(12, 18) = 36 days. Tiling: You want to tile a floor that's 252 cm × 105 cm with square tiles (no cutting). The largest possible tile size is GCD(252, 105) = 21 cm. Gear ratios: In mechanical systems, the LCM of two gear tooth counts determines how many rotations before the teeth align again.Multiple Numbers
For three or more numbers:
GCD(a, b, c) = GCD(GCD(a, b), c)
LCM(a, b, c) = LCM(LCM(a, b), c)
Apply the operation pairwise, rolling in one number at a time. The calculator handles this automatically.
Example: GCD(24, 36, 60)- GCD(24, 36) = 12
- GCD(12, 60) = 12
What's the difference between GCD and HCF?
They're the same thing — just different names. GCD (Greatest Common Divisor) is the American/mathematical convention; HCF (Highest Common Factor) is the British/school textbook convention. Same calculation, same result.
Can the GCD of two numbers ever be 1?
Yes, and when that happens the numbers are called coprime (or relatively prime). GCD(14, 15) = 1 — they share no common factors. This is important in cryptography, where key generation relies on choosing coprime numbers.
Why does GCD × LCM = product of the two numbers?
It's a consequence of prime factorization. Each prime factor's contribution gets distributed between the GCD (minimum powers) and LCM (maximum powers), and together they account for all prime factors exactly as the original product does. Works only for exactly two numbers, not three or more.
Related calculators: Fraction Calculator · Exponent Calculator · Scientific Calculator