Lowest common multiple of two numbers

Martin McBride
2022-01-27

The lowest common multiple (LCM) of two integers a and b is the smallest positive integer that is divisible by both a and b.

It is usually written as lcm(a, b).

We can find the LCM of two numbers by looking at the multiples of each number, and comparing them to find the smallest number that appears in both lists. For example, to find the LCM of 12 and 18:

  • Multiples of 12 are 12, 24, 36, 48, 60, 72...
  • Multiples of 18 are 18, 36, 54, 72, 90, 108...

Comparing the lists, the lowest common multiple is 36 (ie 12 multiplied by 3, or 18 multiplied by 2).

LCM and prime factors

The LCM can be found from the prime factors of the two numbers. For example:

$$ \begin{align} 18 = 2 \times 3 \times 3 \newline 12 = 2 \times 2 \times 3 \end{align} $$

For each prime factor we take the highest multiplicity for either number:

  • For 2, the highest multiplicity is 2 that occurs in the number 12.
  • For 3, the highest multiplicity is 3 that occurs in the number 18.

The LCM of 12 and 18 is therefore:

$$ 2^2 \times 3^2 = 4 \times 9 = 36 $$

LCM and GCD

The greatest common divisor (GCD) of two integers a and b is the largest positive integer that divides into both a and b.

The LCM can also be found using this formula:

$$ lcm(a, b) = \frac{a.b}{gcd(a, b)} $$

For 12 and 18, the GCD is 6 (6 is the largest number that divides into both 12 and 18), so:

$$ lcm(12, 18) = \frac{12 \times 18}{6} = 36 $$

The linked article gives a method for calculating the GCD, known as Euclid's Algorithm.