GCD LCM Calculator

The greatest common divisor, or GCD, is the largest positive integer that divides two or more integers without remainder. The least common multiple, or LCM, is the smallest positive integer that each of the numbers divides. Together they describe how whole numbers share factors and align on repeated cycles.

For example, the GCD of 18 and 24 is 6 because 6 is the largest factor common to both. The LCM is 72 because 72 is the first positive number that is a multiple of both. One concept looks downward toward shared factors; the other looks upward toward shared repetitions.

Prime factorization makes the relationship clear. Break each number into primes, then compare powers of each prime. The GCD uses the minimum shared powers; the LCM uses the maximum powers needed to cover all numbers. For 18 = 2 x 3^2 and 24 = 2^3 x 3, the GCD is 2 x 3 = 6 and the LCM is 2^3 x 3^2 = 72.

This method is intuitive, but factoring large numbers can be expensive. For everyday arithmetic it is fine. For large integers, algorithms such as Euclid's method are more efficient for finding the GCD.

Euclid's algorithm finds the GCD by repeated division with remainder. The central fact is that gcd(a, b) equals gcd(b, a mod b). Repeating this step shrinks the numbers until the remainder is zero; the last nonzero remainder is the GCD.

This algorithm is ancient, fast, and foundational. It appears in fraction simplification, modular arithmetic, cryptography, computer algebra, and number theory. It works because subtracting or removing whole multiples of one number from another does not change their common divisors.

GCD is used to reduce fractions, find common units, simplify ratios, and reason about divisibility. LCM is used to add fractions with different denominators, schedule repeating events, align cycles, and solve modular timing problems.

The two are connected by the identity gcd(a, b) x lcm(a, b) = |a x b| for positive integers. That relationship shows they are not separate tricks; they are complementary views of the same factor structure.