GCD & LCM Calculator
Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two or more numbers. See step-by-step prime factorization and Euclidean algorithm working. 100% private — runs in your browser.
How to Calculate GCD and LCM
The Greatest Common Divisor (GCD), also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers without leaving a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of all the given numbers. Both are fundamental concepts in number theory with wide applications in mathematics and everyday problem-solving.
There are two main methods to find the GCD: prime factorization and the Euclidean algorithm. This calculator shows both methods step by step so you can learn and verify the process.
Key Formulas
GCD(a, b) = GCD(b, a mod b) — Euclidean Algorithm
LCM(a, b) = |a × b| / GCD(a, b)
GCD(a, b) × LCM(a, b) = |a × b|
For prime factorization method:
- GCD = product of common prime factors, each to the lowest power
- LCM = product of all prime factors, each to the highest power
Example: GCD and LCM of 48 and 36
Method 1: Prime Factorization
- 48 = 2&sup4; × 3
- 36 = 2² × 3²
- GCD = 2² × 3 = 12 (lowest powers of common primes)
- LCM = 2&sup4; × 3² = 144 (highest powers of all primes)
Method 2: Euclidean Algorithm
- 48 = 36 × 1 + 12
- 36 = 12 × 3 + 0
- GCD = 12 (last non-zero remainder)
- LCM = 48 × 36 / 12 = 144
The Euclidean Algorithm
The Euclidean algorithm is one of the oldest algorithms still in use, dating back to around 300 BCE. It works by repeatedly applying the division algorithm: divide the larger number by the smaller, then replace the larger number with the smaller and the smaller with the remainder. Continue until the remainder is zero. The last non-zero remainder is the GCD. This method is much faster than prime factorization for large numbers.
Applications of GCD and LCM
GCD is used to simplify fractions (divide numerator and denominator by their GCD), solve Diophantine equations, and in modular arithmetic for cryptography. LCM is used in adding fractions (finding common denominators), scheduling problems (when will two events coincide?), and gear ratio calculations. In programming, GCD is used in hash functions, grid layout calculations, and aspect ratio simplification.
GCD and LCM for Multiple Numbers
To find the GCD of more than two numbers, compute it iteratively: GCD(a, b, c) = GCD(GCD(a, b), c). The same approach works for LCM: LCM(a, b, c) = LCM(LCM(a, b), c). This calculator supports any number of inputs separated by commas.