GCD and LCM Calculator

How to use the GCD and LCM calculator

1. Type your numbers in Whole numbers, separated by spaces, commas, semicolons or new lines: for example 84 126 210.
2. The GCD (greatest common divisor) and LCM (least common multiple) appear as you type. Calculate does the same, and Copy copies both results.
3. Below the results, three panels show the working: Euclidean algorithm, Prime factorization method and LCM from the GCD: LCM(a, b) = a × b / GCD(a, b).

You can enter up to 50 numbers, each with up to about 6,000 digits. Signs are ignored, since divisors and multiples are the same for −12 and 12. Simple powers such as 2^32 are accepted as long as they contain no spaces.

What the GCD and LCM are

The greatest common divisor (GCD, also called greatest common factor, GCF, or highest common factor, HCF) is the largest whole number that divides every number in the list without a remainder. For 84, 126 and 210 it is 42.

The least common multiple (LCM) is the smallest positive number that is a multiple of every number in the list. For 84, 126 and 210 it is 1260.

Typical uses: the GCD simplifies fractions (84/126 = 2/3 after dividing both by 42) and cuts things into the largest equal pieces; the LCM gives the lowest common denominator when adding fractions, and tells you when repeating cycles line up again (two buses every 12 and 18 minutes meet every 36 minutes).

When the GCD is 1, the numbers are coprime (relatively prime): they share no factor, like 8 and 15. The tool says so, and otherwise shows each number divided by the GCD.

Method 1: the Euclidean algorithm

Euclid’s method replaces the larger number by the remainder of the division, again and again, until the remainder is 0. The last nonzero remainder is the GCD:

• 1071 = 2 × 462 + 147
• 462 = 3 × 147 + 21
• 147 = 7 × 21 + 0, so GCD(1071, 462) = 21.

It is fast even for numbers with hundreds of digits, which is why the result is always exact. With three or more numbers, it is applied pair by pair: GCD(a, b, c) = GCD(GCD(a, b), c).

Method 2: prime factorization

Write each number as a product of primes. The GCD takes every prime common to all numbers with its smallest exponent; the LCM takes every prime that appears with its largest exponent. With 12 = 2² × 3 and 18 = 2 × 3²: GCD = 2 × 3 = 6 and LCM = 2² × 3² = 36. This method is shown whenever every number can be factored quickly; for very large numbers the Euclidean algorithm still gives the answer.

Method 3: LCM from the GCD

For two numbers, GCD × LCM = a × b, so LCM(a, b) = a × b / GCD(a, b). For 12 and 18: 12 × 18 / 6 = 36. For a longer list, the rule is applied step by step.