GCD & LCM Calculator

What Are GCD and LCM?

The Greatest Common Divisor (GCD), also known as 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. For example, the GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly. The GCD plays a fundamental role in simplifying fractions, solving Diophantine equations, and optimizing algorithms throughout computer science and mathematics.

The Least Common Multiple (LCM) is the smallest positive integer that is divisible by two or more given numbers. For instance, the LCM of 4 and 6 is 12, because 12 is the smallest number that both 4 and 6 divide into evenly. The LCM is essential in adding and subtracting fractions with different denominators, scheduling recurring events, and solving problems involving periodicity and synchronization.

The Euclidean Algorithm

The Euclidean algorithm is one of the oldest and most efficient methods for computing the GCD of two numbers. Dating back to around 300 BCE when Euclid described it in his monumental work “Elements,” this algorithm remains widely used in modern computing today. The algorithm works on a beautifully simple principle: the GCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number. This process repeats until the remainder is zero, at which point the last non-zero remainder is the GCD.

For example, to find GCD(48, 18): divide 48 by 18 to get a remainder of 12. Then divide 18 by 12 to get remainder 6. Then divide 12 by 6 to get remainder 0. Since the remainder is now zero, the GCD is 6. This algorithm is remarkably efficient even for very large numbers, with a time complexity of O(log(min(a, b))), making it one of the fastest known methods. The extended Euclidean algorithm further allows you to express the GCD as a linear combination of the two original numbers, which is critical in cryptography and modular arithmetic.

Prime Factorization Method

Another approach to computing GCD and LCM uses prime factorization. Every positive integer greater than 1 can be uniquely represented as a product of prime numbers, a principle known as the Fundamental Theorem of Arithmetic. To find the GCD using prime factorization, you express each number as a product of primes, then take the lowest power of each common prime factor. For the LCM, you take the highest power of each prime factor that appears in any of the factorizations.

Consider the numbers 60 and 48. The prime factorization of 60 is 2^2 x 3 x 5, and for 48 it is 2^4 x 3. The GCD takes the minimum exponent for each common prime: 2^2 x 3 = 12. The LCM takes the maximum exponent for each prime that appears: 2^4 x 3 x 5 = 240. While prime factorization is more intuitive for understanding the relationship between numbers, the Euclidean algorithm is generally faster for computation, especially with large numbers where factorization becomes computationally expensive.

The Relationship Between GCD and LCM

GCD and LCM share a fundamental mathematical relationship expressed by the formula: LCM(a, b) = |a x b| / GCD(a, b). This elegant identity means that once you know the GCD of two numbers, computing the LCM is straightforward and requires no additional factorization. This relationship also reveals that for any two positive integers, their product equals the product of their GCD and LCM: a x b = GCD(a, b) x LCM(a, b). This identity extends to multiple numbers through iterative application, computing the GCD or LCM of the first two numbers, then combining that result with the third number, and so on.

Real-World Applications

GCD and LCM have extensive practical applications across many disciplines. In everyday mathematics, the GCD is used to simplify fractions to their lowest terms. To simplify 24/36, divide both numerator and denominator by their GCD of 12 to get 2/3. The LCM is crucial when adding fractions with different denominators, as you need a common denominator to perform the addition.

In computer science, the GCD is fundamental to the RSA encryption algorithm, one of the most widely used public-key cryptographic systems. It is also used in hash table design, computer graphics for pixel aspect ratios, and data compression algorithms. In engineering and manufacturing, the LCM helps determine when gears of different sizes will simultaneously return to their starting positions, and the GCD helps find the largest tile size that can evenly cover a floor of given dimensions. In music theory, the LCM of frequencies determines when two periodic sound waves will realign, which relates to the concept of consonance and harmony.

Tips for Using This Calculator

This calculator supports up to 10 positive integers and provides step-by-step solutions so you can follow the computation process. For two numbers, the full Euclidean algorithm is displayed showing each division step. For three or more numbers, the calculator shows how it iteratively applies GCD and LCM to pairs of numbers. The prime factor table visualizes how the minimum and maximum exponents determine the GCD and LCM respectively. Use the all-factors view to see every divisor of each number, with common factors of the GCD highlighted for easy identification. All computations are performed entirely in your browser with no data sent to any server.