4.3: Least Common Multiple
- Page ID
- 7531
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \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}}\)
\( \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}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Definition: Least Common Multiples
Let \(a\) and \(b\) be integers. Then any integer that is a multiple of both \(a\) and \(b\) is called a common multiple of \(a\) and \(b\). The least common multiple of integers a and b, denoted by \(lcm(a,b)\), is the smallest positive common multiple of \(a\) and \(b\).
Example \(\PageIndex{1}\):
Find
1. \(lcm(5,10)\)
2. \(lcm(-6,18)\)
3. \(lcm(0,5)\)
Solution
1. \(10\), 2. \(18\) 3. undefined.
Finding LCM using GCD
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{2}\):
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.
\(\frac{(24)(35)}{1}= 840.\)
Hence \(lcm(24,35)=840.\)
Properties:
Let \(a,b,c \in \mathbb{Z}\).
Then:
- \(lcm(a, a)=a.\)
- \(lcm(a, b)=lcm(b, a)\).
- \(lcm(a,b,c)=lcm (lcm(a, b), c)=lcm(a, lcm(b, c))\).
- \(lcm(a,0)=\) undefined.
Example \(\PageIndex{3}\):
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 \( lcm (2, 3, 4, 5) - 1 = n.\)
We must now determine the lcm of \(2, 3, 4, 5,\) which is \(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