GCD/LCM Calculator

How Does the Formula Work?

The GCD/LCM calculator finds the Greatest Common Divisor and Least Common Multiple of two or more positive integers. It uses the Euclidean algorithm for efficient GCD computation and the relationship LCM = product divided by GCD for two numbers. For multiple numbers, GCD and LCM are computed iteratively. The calculator also shows the prime factorization of each input number, making the mathematical relationship between the numbers visible. This tool is essential for students learning number theory, simplifying fractions, finding common denominators, and solving divisibility problems in mathematics.

The Euclidean Algorithm

The Euclidean algorithm is one of the oldest known algorithms, described by Euclid around 300 BCE. It finds the GCD by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller. For example, GCD(48, 18): 48 mod 18 = 12, then 18 mod 12 = 6, then 12 mod 6 = 0, so GCD = 6. This method is remarkably efficient — it requires at most 5 times the number of digits in the smaller number. The algorithm works because any common divisor of a and b must also divide their remainder. The Euclidean algorithm is fundamental to modern cryptography (RSA key generation), computer algebra systems, and continued fraction expansions.

Prime Factorization Method

An alternative method uses prime factorization. Factor each number into primes: 12 = 2² × 3, and 8 = 2³. The GCD takes the minimum power of each common prime factor: GCD = 2^min(2,3) = 2² = 4. The LCM takes the maximum power of all prime factors: LCM = 2^max(2,3) × 3^max(1,0) = 2³ × 3 = 24. While this method is more intuitive for understanding, the Euclidean algorithm is computationally faster for large numbers. This calculator shows both the final GCD/LCM result and the prime factorization of each number so you can see both approaches simultaneously.

Practical Applications

GCD and LCM appear throughout mathematics and daily life. Simplifying fractions uses GCD: 12/8 simplifies to 3/2 by dividing both by GCD(12,8) = 4. Adding fractions with different denominators uses LCM: 1/4 + 1/6 needs denominator LCM(4,6) = 12, giving 3/12 + 2/12 = 5/12. Scheduling problems use LCM: if bus A comes every 12 minutes and bus B every 8 minutes, they meet at stop together every LCM(12,8) = 24 minutes. Tiling problems use GCD: the largest square tile that fits perfectly in a 48cm × 36cm room is GCD(48,36) = 12cm. Gear ratio calculations, music rhythm patterns, and cryptographic key generation all rely on GCD and LCM computations.

Number Theory Connections

GCD and LCM are fundamental to number theory. Two numbers with GCD = 1 are called coprime or relatively prime — they share no common factors other than 1. Euler's totient function, which counts integers less than n that are coprime to n, is central to RSA encryption. The fundamental theorem of arithmetic states that every integer greater than 1 has a unique prime factorization, which is what makes the prime factorization method for GCD/LCM work. Bezout's identity guarantees that for any integers a and b, there exist integers x and y such that ax + by = GCD(a,b) — this is used in the extended Euclidean algorithm. Enter your numbers to find GCD, LCM, and prime factorizations instantly — from basic fraction work to advanced number theory, this calculator covers it all.