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\)