GCD & LCM Calculator
Find the Greatest Common Divisor (GCD/HCF) and Least Common Multiple (LCM) with step-by-step Euclidean algorithm remainders.
Supports 2, 3, or more integers with step-by-step Euclidean remainder division.
The largest positive integer that divides all entered numbers without a remainder.
The smallest positive integer that is divisible by all entered numbers.
Prime Factorization Method:
Euclidean Algorithm Step-by-Step Table
Dividend = Divisor × Quotient + Remainder (repeating until remainder = 0)| Step | Dividend (a) | Divisor (b) | Quotient (q) | Remainder (r) | Equation |
|---|---|---|---|---|---|
| #1 | 180 | 48 | 3 | 36 | 180 = 48 × 3 + 36 |
| #2 | 48 | 36 | 1 | 12 | 48 = 36 × 1 + 12 |
| #3 | 36 | 12 | 3 | 0 | 36 = 12 × 3 + 0 |
GCD(a, b) × LCM(a, b) = |a × b| → 12 × 720 = 8640 (matches 48 × 180 = 8640)Number Theory: Divisors, Multiples & Euclidean Algorithm
The Euclidean Algorithm
Formulated around 300 BC by Euclid of Alexandria in Elements, this is one of the oldest numerical algorithms still in widespread use.
It exploits the theorem that GCD(a, b) = GCD(b, a mod b). Repeating this division produces remainders that decrease rapidly until zero is reached; the last non-zero remainder is the GCD.
Prime Factorization Method
Express both numbers as products of prime factors. For each distinct prime factor:
- GCD: Take the minimum power of common prime factors.
- LCM: Take the maximum power of all prime factors appearing in either number.
Example: 48 = 2⁴ × 3¹ and 180 = 2² × 3² × 5¹. GCD = 2² × 3¹ = 12; LCM = 2⁴ × 3² × 5¹ = 720.
Fundamental Product Identity
For any two positive integers a and b, the product of their greatest common divisor and least common multiple always equals the product of the numbers:
When GCD(a, b) = 1, the numbers are coprime (mutually prime), and their LCM is simply a × b.