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.

GCD and LCM in Computer Science

GCD computation is fundamental to several areas of computer science. The RSA cryptographic algorithm uses the extended Euclidean algorithm to compute modular multiplicative inverses; a key step in generating public and private keys that secure internet communications. Fraction arithmetic in computer algebra systems relies on GCD to keep fractions in lowest terms automatically. Hash tables use the same idea from two directions: the table size is often chosen to be a prime, and double hashing needs the probe step to be coprime to that size, because if the step and the size share a divisor d the probe sequence only ever reaches one slot in every d. Audio and video processing use LCM for synchronizing different sample rates and frame rates. Computational geometry uses GCD for reducing rational coordinates to simplest form. The binary GCD algorithm (Stein's algorithm) uses only subtraction and bit shifting, making it faster on hardware without efficient division. Understanding GCD and LCM provides insight into fundamental mathematical structures that underpin modern computing.

Working with Large Numbers

The Euclidean algorithm is remarkably efficient even for very large numbers. Finding the GCD of two 100-digit numbers requires at most about 500 steps; fast enough for real-time computation. This efficiency is what makes GCD practical in cryptography where numbers have hundreds or thousands of digits. The algorithm's efficiency was proven by Gabriel Lamé in 1844; the worst case occurs when the inputs are consecutive Fibonacci numbers. You can enter values up to 9,007,199,254,740,991, the largest integer JavaScript represents exactly, and the GCD is exact across that whole range. The LCM is accumulated with exact integer arithmetic rather than floating point, so it stays correct even when the answer itself grows past that limit: LCM(123456789, 987654321) returns 13548070123626141, with the final digit intact. Enter your numbers separated by commas or spaces and get GCD, LCM, and prime factorizations instantly; the essential number theory tool for students, teachers, and professionals.