LCM & GCD Calculator

The GCD is the largest positive integer that divides all given numbers without remainder.

Use the Euclidean algorithm for efficient calculation: repeatedly divide and take remainders until you reach 0.

The LCM is the smallest positive integer divisible by all given numbers.

Calculate using prime factorization (take highest powers) or the formula: LCM = (a × b) / GCD.

The GCD (greatest common divisor) is the largest integer that divides every given number exactly, while the LCM (least common multiple) is the smallest positive integer that every given number divides into exactly.

They pull in opposite directions: GCD looks downward to the biggest shared factor, LCM looks upward to the smallest shared multiple. For 12 and 18, the GCD is 6 and the LCM is 36.

According to Wolfram MathWorld, the GCD is also written gcd(a, b) or (a, b), and the term "highest common factor" (HCF) is a common British synonym for the same quantity.

The Euclidean algorithm finds the GCD by repeatedly replacing the larger number with the remainder of dividing it by the smaller, stopping when the remainder reaches zero; the last non-zero remainder is the GCD.

For 48 and 18: 48 = 2×18 + 12, then 18 = 1×12 + 6, then 12 = 2×6 + 0, so gcd(48, 18) = 6.

Encyclopaedia Britannica notes this method dates to Euclid's Elements (c. 300 BCE), making it one of the oldest algorithms still in everyday use. Its efficiency is why software libraries use it instead of factoring large numbers.

To find the LCM by prime factorization, factor each number into primes, then multiply every prime raised to its highest power appearing in any factorization.

For 12 = 2²×3 and 18 = 2×3², take 2² and 3², giving LCM = 4×9 = 36. For the GCD, instead take each shared prime at its lowest power: 2¹×3¹ = 6.

Khan Academy teaches this side-by-side comparison because it makes the LCM/GCD contrast visual. Prime factorization is intuitive for small numbers but slower than the Euclidean algorithm for large ones, since factoring is computationally hard.

For any two positive integers a and b, LCM(a, b) × GCD(a, b) = a × b. This identity lets you compute one quantity from the other: LCM(a, b) = (a × b) / GCD(a, b).

For 12 and 18, GCD is 6, so LCM = (12 × 18) / 6 = 216 / 6 = 36, and indeed 6 × 36 = 216 = 12 × 18.

Wolfram MathWorld documents this relation as the standard bridge between the two functions. Note the formula holds only for two numbers; for three or more, you apply it pairwise rather than assuming the product equals LCM × GCD.

For three or more numbers, apply the GCD or LCM pairwise: compute the result of the first two, then combine that with the next number, and so on.

For example, gcd(12, 18, 24) = gcd(gcd(12, 18), 24) = gcd(6, 24) = 6, and lcm(4, 6, 8) = lcm(lcm(4, 6), 8) = lcm(12, 8) = 24. Both operations are associative, so the grouping order does not change the answer.

This calculator handles batches automatically, but the shortcut LCM×GCD = product does not extend to three or more inputs, a point Wolfram MathWorld emphasizes.

Two numbers are coprime (relatively prime) when their GCD equals 1, meaning they share no prime factors even if neither is prime itself.

For example, gcd(8, 15) = 1: 8 = 2³ and 15 = 3×5 have no common prime, so they are coprime. When numbers are coprime, their LCM equals their product; lcm(8, 15) = 120 = 8×15.

Wolfram MathWorld notes coprimality underpins modular arithmetic and RSA cryptography, where key generation requires an exponent coprime to Euler's totient. Coprimality is a property of the pair, not of the individual numbers.

LCM and GCD appear far beyond textbooks.

GCD simplifies fractions to lowest terms (12/18 reduces to 2/3 after dividing by 6) and finds the largest equal-size groups when distributing items — and once those groups are fixed, a factorial calculator counts the ways to arrange the items within each one.

LCM finds when repeating events coincide, such as two buses departing every 12 and 18 minutes meeting again after 36 minutes, and it produces the common denominator for adding fractions.

Engineers use GCD in gear-ratio and timing-belt design, while cryptographers rely on coprimality checks (GCD = 1) during RSA key setup, as Encyclopaedia Britannica describes in its coverage of number theory applications.

Bézout's identity states that for integers a and b, there exist integers x and y such that ax + by = gcd(a, b).

For 12 and 18, gcd is 6, and one solution is 12×(−1) + 18×(1) = −12 + 18 = 6. The extended Euclidean algorithm computes these coefficients while it computes the GCD, which is exactly how modular inverses are found in cryptography.

Wolfram MathWorld and the NIST Digital Library of Mathematical Functions both treat Bézout's identity as a cornerstone result of elementary number theory, since it guarantees a linear combination equal to the GCD always exists.

Several common errors trip people up when computing LCM and GCD:

• A frequent error is swapping the two: the GCD is never larger than the smallest input, while the LCM is never smaller than the largest input, so check your answer against that bound.

• Another mistake is assuming LCM × GCD = product works for three or more numbers, which it does not.

• People also forget that GCD and LCM are defined for positive integers, not fractions or decimals, so inputs must be whole numbers.

• Finally, when numbers are coprime, remember the GCD is 1 (not 0), and the LCM equals their product.

Verifying with the identity LCM×GCD = a×b catches most two-number slip-ups.