4.3: Least Common Multiple
( \newcommand{\kernel}{\mathrm{null}\,}\)
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 4.3.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)=|ab|gcd(a,b)
Example 4.3.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.
(24)(35)1=840.
Hence lcm(24,35)=840.
Properties:
Let a,b,c∈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 4.3.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(mod2)≡1
n(mod3)≡2
n(mod4)≡3
n(mod5)≡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 4.3.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≡8(mod11),
x≡10(mod13),
x≡12(mod15),
x≡14(mod17).
Since x≡8(mod11), possible values for x are 8,19,30,41,52,...,8+11m where m∈Z.
Since x≡10(mod13), possible values for x are 10,23,46,59,72,...,10+13k where k∈Z.
Since x≡8(mod11) and x≡10(mod13), x=lcm(11,13)−3.
By similar argument, we can see that if x≡8(mod11), x≡10(mod13), x≡12(mod15), and x≡14(mod17).
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