GCD & LCM Calculator

About This Tool

The GCD and LCM Calculator computes the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two or more integers using two complementary methods: the Euclidean algorithm and prime factorization. It shows detailed step-by-step solutions for both approaches, making it an excellent learning tool for students studying number theory, discrete mathematics, or preparing for standardized tests. Understanding GCD and LCM is fundamental to working with fractions, modular arithmetic, and many areas of computer science.

The Euclidean Algorithm

The Euclidean algorithm is one of the oldest algorithms still in common use, dating back to Euclid's Elements (circa 300 BCE). It computes the GCD of two integers by repeatedly applying the division algorithm: divide the larger number by the smaller, then replace the larger with the smaller and the smaller with the remainder. When the remainder reaches zero, the last non-zero remainder is the GCD. The algorithm is remarkably efficient, running in O(log(min(a,b))) steps, which makes it practical even for very large numbers. The extended Euclidean algorithm also finds integers x and y such that ax + by = gcd(a,b), which is essential for computing modular inverses in cryptography.

Prime Factorization Method

The prime factorization method works by decomposing each number into its prime factors. The GCD is then the product of all common prime factors raised to their minimum power, and the LCM is the product of all prime factors raised to their maximum power. For example, if a = 2^3 times 3^2 and b = 2^2 times 3^3, then GCD = 2^2 times 3^2 = 36 and LCM = 2^3 times 3^3 = 216. While this method is more intuitive and educational, it requires finding the prime factorization of each number, which is computationally expensive for very large numbers. The Euclidean algorithm is preferred in practice for its efficiency.

The GCD-LCM Relationship

For any two positive integers a and b, the product of their GCD and LCM equals the product of the numbers themselves: GCD(a,b) times LCM(a,b) = a times b. This elegant relationship provides a quick way to compute the LCM once you know the GCD: LCM(a,b) = (a times b) / GCD(a,b). It also explains why numbers that share many common factors (large GCD) have a relatively small LCM, and vice versa. Coprime numbers (GCD = 1) have LCM equal to their product. This relationship extends to prime factorizations: taking the min of exponents (GCD) and the max (LCM) for the same set of primes naturally satisfies this identity.

Applications of GCD

The GCD has numerous practical applications. In fraction simplification, dividing the numerator and denominator by their GCD gives the fraction in lowest terms. In cryptography, the extended Euclidean algorithm computes modular inverses needed for RSA encryption. In music theory, the GCD of two frequencies determines their interval relationship. In tiling problems, the GCD of two dimensions determines the largest square tile that can perfectly cover a rectangle. Computer scientists use GCD in the Stern-Brocot tree for efficient rational number representation and in algorithms for computing continued fractions.

Applications of LCM

The LCM is used whenever you need to synchronize cycles or find common denominators. Adding fractions with different denominators requires finding the LCM of the denominators (the least common denominator). In scheduling, the LCM tells you when two periodic events will next coincide: if one event occurs every 12 days and another every 18 days, they coincide every LCM(12,18) = 36 days. In gear systems, the LCM of tooth counts determines when the gears return to their starting position. In number theory, the LCM appears in the Chinese Remainder Theorem and Carmichael's function.

Extending to Multiple Numbers

Both GCD and LCM extend naturally to more than two numbers. GCD(a,b,c) = GCD(GCD(a,b), c), and similarly for LCM. This associative property means you can compute the GCD or LCM of any number of integers by iterating pairwise. This calculator supports multiple inputs, computing both the pairwise Euclidean algorithm steps (for the first two numbers) and the prime factorization across all numbers. For the prime factorization method with multiple numbers, the GCD uses the minimum exponent across all factorizations, and the LCM uses the maximum exponent.