Number Theory
Least Common Multiple
LCM applications
Type 1:
Suppose there are certain chocolates which are to be distributed in a class equally among all the students. If we distribute 8 chocolates per head, last student gets only 1 chocolate and if we distribute 5 chocolates per head last student again gets 1 chocolate only. By this data we can conclude that number of chocolates is one more than multiple of 8 and one more than multiple of 5. Hence the number of chocolates = \(8{k_1} + 1{\rm{ }} = {\rm{ }}5{k_2} + 1\).
The same question can be framed as to find the number which when divided by 8 and 5 remainders are 1 in each case. If the remainders are same, the number is of the form of \(8{k_{1\;}} + \;1\; = \;5{k_{2\;}} + \;1\) so the number is LCM of (5 and 8) + 1 = 41.
Or the general number of this type = \(40 k +1\)
General number which when divided by \({n_1},{n_2},{n_3},\)…. remainders are same in each case and is equal to \(r\), is: \(N k + r\), where \(N\) is LCM of \({n_1},{n_2},{n_3},\)……
Type 2:
Take the same example as discussed above, there are certain chocolates which are to be distributed in a class equally among all the students. If we distribute 8 chocolates per head, last student gets only 7 chocolate and if we distribute 5 chocolates per head last student again gets 4 chocolate only. By this data we can conclude that number of chocolates is one less than multiple of 8 and one less than multiple of 5. Hence the number of chocolates = \(8{k_1}-{\rm{ }}1{\rm{ }} = {\rm{ }}5{k_2}-{\rm{ }}1\).
The same question can be framed as to find the number which when divided by 8 and 5 remainders are 7 and 4 respectively.
Or the general number of this type = \(40 k - 1\)
General number which when divided by \(a, b, c\), remainders are \((a - r), (b - r), (c - r)\) etc., is \(Nk – r\), where \(N\) is LCM of \(a, b, c,\)……
Example 8: Find the smallest positive number which when divided by 7, 11 and 13, remainders are 6, 10 and 12.
Solution: Number when divided by 7 remainder is 6, which means number is one less than multiple of 7, similarly number is one less than multiple of 11 and 13.
The remainders are \((7 - 1), (11 - 1)\) and \((13 - 1)\), hence the smallest number is
(LCM of 7, 11 and 13) – 1 = 1001 – 1 = 1000
Type 3:
In some cases remainders are neither equal nor they form any pattern; in this type of case we use algebraic equation to solve such questions. The following example will explain the complete process
Example 9: Find the smallest number which when divided by 7, 11 and 13 corresponding remainders are 1, 3 and 4.
Solution: Suppose the required number is \(n\)
\(n = {\rm{ }}7{k_1} + {\rm{ }}1{\rm{ }} = {\rm{ }}11{k_2} + {\rm{ }}3\)
\(7{k_1}\; = {\rm{ }}11{k_2} + {\rm{ }}2{\rm{ }} = {\rm{ }}7{k_2} + {\rm{ }}\left( {4{k_2} + {\rm{ }}2{\rm{ }}} \right)\)
Now \(\left( {4{k_2} + {\rm{ }}2{\rm{ }}} \right)\) must be multiple of 7, hence \({k_2} = {\rm{ }}3\). Smallest value of the number \(n\) can be \(11x3 + 3 = 36\). Hence \(n\) is off the form of \(77 m + 36\) that should be equal to \(n = 13n + 4\)
Hence \(13n =77m + 32\) or \(13n =78m +26 + (- m + 6)\)
Now \((6 - m)\) should be multiple of 13 or zero. So \(m = 6\).
Number is \(77 \times 6{\rm{ }} + {\rm{ }}36\; = {\rm{ }}462{\rm{ }} + {\rm{ }}36{\rm{ }} = {\rm{ }}498\)