Number Theory
Remainder Theorem
Let us have a look on this table showing corresponding remainders, when multiples of 13 are divided by 11.\[\frac{{13}}{{11}} \equiv 2\]\[\frac{{13 \times 2}}{{11}} \equiv 4\]\[\frac{{{{13}^2}}}{{11}} \equiv 4\]\[\frac{{{{13}^3}}}{{11}} \equiv 8\]
here we are using a sign \(\equiv\) for remainder. We observe that if a number is doubled, corresponding remainder is also doubled, similarly if number is tripled, corresponding remainder is also tripled. This pattern can be proved by using simple algebraic equations. When a number \(p\) is divided by \(q\) remainder is \(r\), so we can write \(p = qk +r,\), then\[2p =2qk +2r\]\[3p =3qk +3r\]\[{p^2} = {q^2}{k^2} + {\rm{ }}2qkr{\rm{ }} + {\rm{ }}{r^2}\].
So to find remainder in a big multiplication or exponent of numbers, we can just replace each numbers by corresponding remainders. For example to find remainder when \(1924 \times 1925 \times 1926\) is divided by 1923.\[\frac{{\mathop {(1924)}\limits^1 \times \mathop {(1925)}\limits^2 \times \mathop {(1926}\limits^3 )}}{{1923}} = {\rm{ }}1 \times 2 \times 3{\rm{ }} = {\rm{ }}6\]
Concept of negative remainder:
We can use negative remainder in calculations, however the final answer must be a positive remainder. Suppose we divide 15 by 16 then the remainder can be +15 or – 1. For calculations –1 remainder is far more easier to handle than 15. So we will use the remainder positive or negative whichever is smaller. Let us take an example:\[\frac{{{3^{21}}}}{{14}} \equiv \frac{{{{\left( {{3^3}} \right)}^7}}}{{14}} \equiv \frac{{{{27}^7}}}{{14}} \equiv \frac{{{{( - 1)}^7}}}{{14}} \equiv - 1\]
Since the final remainder cannot be negative, hence it should be 13.
Example 2: Find the remainder when \(192{4^{192{5^{1926}}}}\) is divided by 1925.
Solution: Since \({1925^{1926}}\) is an odd number, so question is similar to \({1924^{{\rm{odd}}\;{\rm{number}}}}\) is divided by 1925.
\[\frac{{{{1924}^{{\rm{odd}}\;{\rm{number}}}}}}{{1925}} \equiv \frac{{{{( - 1)}^{{\rm{odd}}\;{\rm{number}}}}}}{{1925}} = - 1\;{\rm{or}}\;1924\]
Example 3: Find the remainder when \({2^{100}}\) is divided by 21.
Solution: Nearest power of 2 that is very close to multiple of 21, is 6. We will split the powers of 2 in the group of 6.\[\frac{{{2^{100}}}}{{21}}\,\, \cong \,\frac{{{{({2^6})}^{^{16}}}{{.2}^4}}}{{21}}\, \cong \,\frac{{{{( - 1)}^{16}}.16}}{{21}}\,\, = \,16\]
Example 4: Find the remainder when \({\left[ {6!} \right]^{7{!^{8!}}}}\) is divided by 13.
Solution: Since \(6! = 720\) and \({\left( {7!} \right)^{8!}}\) Is multiple of 4, so the question can be written in the form \({720^{4k}}\) is divided by 13.\[\frac{{{{720}^{4k}}}}{{13}}\,\, \cong \,\frac{{{5^{4k}}}}{{13}}\,\, \cong \,\frac{{{{25}^{2k}}}}{{13}}\,\, \cong \frac{{{{( - 1)}^{2k}}}}{{13}}\,\, = 1\]