Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

4.3 Least Common Multiple

 

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

Definition

The least common multiple of integers a and b, also known as the LCM, is the smallest number that is divisible by both integers a and b. You can determine the LCM by dividing the absolute value of the product of a and b by the GCD of \(a\) and \(b\).

That is
\[  lcm(a,b)= \displaystyle \frac{|ab|}{gcd(a,b)}\]

Example \(\PageIndex{1}\):

What is the LCM of 24 and 35?
Solution:
We must first determine the GCD of 24 and 35.
    Find the divisors of 24 and 35.
        24: 1, 2, 3, 4, 8, 12, 24
        35: 1, 5, 7, 35
    Therefore the GCD of 24 and 35 is 1.

Now that we have determined the GCD, we can continue on to determine the least common multiple.
    (24)(35)/1= 840.

The LCM of 24 and 35 is 840.

Example \(\PageIndex{2}\):

A lady is carrying a grocery basket full of chocolate Easter bunnies.  She drops the basket and all the chocolate bunnies break.  When asked how many chocolate bunnies she had, she says that she is poor in arithmetic, but remembers that when she counted the chocolate bunnies by twos, threes, fours and fives she had remainders of 1, 2, 3, and 4 respectively.  What is the smallest number of chocolate bunnies that she could have had in the basket?
Solution:
At First, this problem uses modular arithmetic and lcm together.
    Let n= the number of chocolate bunnies. Then 
        \(n(mod\, 2)  \equiv 1 \)
        \(n(mod \,3) \equiv 2 \) 
        \(n(mod \,4) \equiv 3 \) 
        \(n(mod\, 5) \equiv   4\)
    This shows us that the lcm of 2, 3, 4, 5 = n + 1.

We need to subtract the 1 from either side to isolate n.
    Therefore the lcm  (2, 3, 4, 5) - 1 = n.

We must now determine the lcm of 2, 3, 4, 5. 
    60 - 1 = 59.

Therefore the smallest number of chocolate bunnies the lady could have had in her shopping basket was 59.

Example \(\PageIndex{3}\):

Find the smallest positive integer \(x\)  with following condition: \(x\) has remainders \(8, 10, 12,\) and \(14\) when divided by \(11, 13, 15,\) and \(17\).
Solution:
We need to find smallest \(x\)  such that
    \(x \equiv 8 (mod \, 11)\),
    \(x \equiv 10 (mod \, 13)\),
    \(x \equiv 12 (mod \, 15)\),
    \(x \equiv 14 (mod \, 17)\).

Since  \(x \equiv 8 (mod \, 11)\), possible values for \(x\) are \( 8, 19, 30, 41, 52, ...,8 + 11m\) where \(m \in \mathbb{Z}.\)
Since  \(x \equiv  10(mod \, 13)\), possible values for \(x\) are \( 10, 23, 46, 59, 72, ...,10 +13k\) where \(k \in \mathbb{Z}.\)
Since \(x \equiv 8 (mod \, 11)\) and  \(x \equiv  10(mod \, 13)\), \(x=lcm(11,13) - 3.\)

By similar argument, we can see that if  \(x \equiv 8 (mod \, 11)\), \(x \equiv 10 (mod \, 13)\), \(x \equiv 12 (mod \, 15)\),  and  \(x \equiv 14 (mod \, 17)\). 
Then \(x=lcm(11, 13, 15, 17) - 3=36465 - 3 = 36462.\)

PRACTICAL USES:

There are multiple real-world applications for using lowest common multiple.

  • Fractions
  • Ratios
  • Recipes
  • Algebra
  • Distribution between packages
  • Meal preparation