Skip to the content

GCD & LCM Calculator

Greatest common divisor and least common multiple of a list of numbers.

Two or more whole numbers, separated by commas, spaces or new lines.

Greatest common divisor (GCD)

6

Least common multiple (LCM)

144

Euclidean algorithm

  1. 48 = 2 × 18 + 12
  2. 18 = 1 × 12 + 6
  3. 12 = 2 × 6 + 0

The remainder has reached 0, so the last divisor is the GCD: 6. The LCM follows from it: 48 × 18 ÷ 6 = 144.

Prime factorizations

48= 24 × 3
18= 2 × 32
GCD= 2 × 3 = 6
LCM= 24 × 32 = 144

The GCD takes each prime that all the numbers share, with the lowest exponent it has anywhere. The LCM takes every prime that occurs, with its highest exponent.

Share this tool:TwitterFacebookLinkedInWhatsAppEmail

What GCD and LCM are for

The greatest common divisor (GCD) of a list of whole numbers is the largest number that divides all of them without a remainder. For 48 and 18 it is 6. The same thing is called the greatest common factor (GCF) or the highest common factor (HCF).

The least common multiple (LCM) is the smallest positive number that all of them divide into. For 48 and 18 it is 144.

You need the GCD to simplify a fraction: divide the top and bottom of 18/48 by 6 and it becomes 3/8. You need the LCM to add or compare fractions with different denominators: 1/48 + 1/18 becomes 3/144 + 8/144 = 11/144, because 144 is the smallest denominator both fit into.

The Euclidean algorithm

Euclid described this method around 300 BC. Divide the larger number by the smaller one. Then divide the previous divisor by the remainder, and repeat until the remainder is 0.

StepDivision
148 = 2 × 18 + 12
218 = 1 × 12 + 6
312 = 2 × 6 + 0

The last divisor, 6, is the GCD. This works because anything that divides both 48 and 18 also divides 48 − 2 × 18 = 12. The pair 18 and 12 therefore has the same common divisors as 48 and 18, and so on down the table, with smaller numbers at every step.

It is fast for numbers of any length. The number of divisions is never more than five times the number of digits of the smaller number, so two numbers of a hundred digits need 500 steps at most. The calculator shows the steps when you enter exactly two numbers.

GCD × LCM = a × b

For two numbers, the GCD times the LCM equals the product of the numbers: 6 × 144 = 864 = 48 × 18. This is how the LCM is worked out here: 48 × 18 ÷ 6 = 144.

The rule holds for two numbers only. For 4, 6 and 10 the GCD is 2 and the LCM is 60, and 2 × 60 is not 4 × 6 × 10. A longer list is handled a pair at a time: the LCM of 4 and 6 is 12, and the LCM of 12 and 10 is 60.

Reading both off the prime factors

48 = 24 × 3 and 18 = 2 × 32. The GCD takes each prime the numbers have in common, with the lowest exponent: 2 × 3 = 6. The LCM takes every prime that occurs, with the highest exponent: 24 × 32 = 144.

The table of factorizations appears for up to eight numbers of at most 1,000,000,000,000. Larger numbers take too long to factor, which the Euclidean algorithm never needs to do. To factor a single large number, use the prime factorization tool.

Coprime, zero and negative numbers

Two numbers with a GCD of 1 are called coprime. Neither has to be prime: 8 and 9 are coprime, and their LCM is simply 8 × 9 = 72.

Every number divides 0, so the GCD of 12 and 0 is 12. The only multiple of 0 is 0 itself, so a list with a zero in it has an LCM of 0. Minus signs are dropped before the calculation, since −6 and 6 have the same divisors.

See all 9