Manager
Joined: 10 Apr 2018
Posts: 187
Given Kudos: 115
Location: United States (NC)
Using Remainder Theorem- Binomial Expression
[#permalink]
16 Mar 2019, 15:34
Hi,
I would share some results that would be helpful for solving remainder type questions.
Say we are asked to find remainder of expression\(\frac{(a+b)^n}{m}\) ------ (I)
How do we approach such questions.
Before , lets see how can we expand \((a+b)^n\).
Using Binomial Expansion we have =\(C^{n}_{0}\) \(a^{n}b^{0}\) +..........+ \(C^{n}_{n}\) \(a^{0}b^{n}\)-------- (II)
now if in expression (I) we have m = a , then we see that in expression (II) each term is divisible by a except the last term \(C^{n}_{n}\) \(a^{0}b^{n}\).
So remainder will be given by the last part.
Well Some important results using binomial expansion we have
if \(\frac{(ax+1)^n}{a}\) remainder is always 1 ----------(I)
eg \(\frac{(37)^{261}}{9}\) = \(\frac{(9*4+1)^{261}}{9}\) in which case remainder is \(\frac{(1)^{261}}{9}\) which is 1 .
or from above we could see it has same form as \(\frac{(ax+1)^n}{a}\) so reminder is 1.
Continuing with the results we also have .
\(\frac{(ax-1)^n}{a}\) reminder is 1 if n is even, remainder is (a-1) is n is odd ----------(II)
eg \(\frac{(31)^{127}}{8}\) \(\frac{(8*4-1)^{127}}{8}\) since n is odd reminder is 8-1 =7
\(\frac{(a)^n}{a+1}\) reminder is 1 if n is even, remainder is a is n is odd ----------(III)
Eg \(\frac{(5)^{126}}{6}\) can be written as \(\frac{(5)^{126}}{5+1}\) Since we have even power the reminder will be 1
\(\frac{(19)^{255}}{20}\) can be written as \(\frac{(19)^{255}}{19+1}\) Since we have even odd power reminder will be 19
How would be the application of above formula in complex situations
the reminder of the expression \(\frac {A* B * C * D * E }{M}\) will be same as reminder of the expression \(\frac {A_r * B_r * C_r * D_r * E_r }{M}\)
where
\(A_r\) is remainder when A is divided by M,
\(B_r\) is remainder when B is divided by M,
\(C_r\) is remainder when C is divided by M,
\(D_r\) is remainder when D is divided by M,
\(E_r\) is remainder when E is divided by M,
here is what i mean
\(\frac {17 * 23 * 11 * 19 * 29 }{12}\) reminder would same as \(\frac {5 * 11 * 11 * 7 * 5 }{12}\)= \(\frac {55 * 55 * 7 }{12}\),the reminder would be same as \(\frac {7 * 7 * 7 }{12}\) or would be same as \(\frac {49* 7 }{12}\) or would be same as \(\frac {7 }{12}\) which is 7.
eg \(\frac {14 * 15}{8}\) = reminder would be same as \(\frac {6 * 7}{8}\) = \(\frac {42}{8}\) so remainder would be 2
or
Using negative reminders we have \(\frac {14 * 15}{8}\) = \(\frac {(-2) * (-1)}{8}\) = \(\frac {2}{8}\)
\(\frac {51 * 52}{53}\) = remainder would be same as \(\frac {(-2) *(-1)}{53}\) remainder would be \(\frac {2}{53}\)
But we need to just take care if we get negative in numerator . Here is what i mean
\(\frac {51 * 52 * 50 }{53}\) = remainder would be same as \(\frac {(-2) *(-1) (-3)}{53}\) remainder would be \(\frac {-6}{53}\) reminder will
53-6 = 47.
Eg. What is the remainder when 73+75+78+57+197
we can use the above formula . \(\frac{73+75+78+57+197}{34}\) remainder will be \(\frac{5+7+10-11-7}{34}\) , \(\frac{4}{34}\) so remainder will be 4
Say we have following examples
(i) find the remainder when each of the following is divided by 7. --------- \(43^{197}\) , \(51^{203}\) , \(59^{28}\) , \(67^{99}\), \(75^{80}\)
(i) find the remainder when each of the following is divided by 17 ----------\(21^{875}\) , \(54^{124}\) , \(83^{261}\) , \(25^{102}\)
\(\frac{43^{197}}{7}\) = \(\frac{(7*6+1)^{197}}{7}\) reminder will be 1 using equation (I)
\(\frac{51^{203}}{7}\) = \(\frac{(7*7+2)^{203}}{7}\) reminder will be same as \(\frac{(2)^{203}}{7}\) , then\((2)^{203}= (2^{3} )^{67} (2)^{2}\), then \(\frac{ (2^{3} )^{67} (2)^{2}}{7}\) which is \(\frac{ (8 )^{67} (2)^{2}}{7}\) which will give \(\frac{ (1 )^{67} (2)^{2}}{7}\)
which will give reminder \(\frac{4}{7}\) hence reminder would be 4 .
\(\frac{59^{28}}{7}\) = \(\frac{(7*8+3)^{28}}{7}\) reminder will be same as \(\frac{(3)^{28}}{7}\) , then\((3)^{28}= (3^{2} )^{14}\), then \(\frac{ (3^{2} )^{14}}{7}\) which is \(\frac{ (9 )^{14}}{7}\) which will give \(\frac{ (2 )^{14}}{7}\) which will give \(\frac{ (2^{3})^{4} (2)^{2}}{7}\)
which will give reminder \(\frac{4}{7}\) hence reminder would be 4 .
\(\frac{67^{99}}{7}\) = we can split this as \(\frac{(7*9+4)^{99}}{7}\) solving it like above we would give remainder as 1
\(\frac{75^{80}}{7}\) = we can split this as \(\frac{(7*11-2)^{80}}{7}\) the reminder will be given by the part \((-2)^{80}\) which is equal to \((2)^{80}\) So \(\frac{(2)^{80}}{7}\) solving it like above we would give remainder as 4
\(\frac{41^{77}}{7}\) = we can split this as \(\frac{(7*6-1)^{77}}{7}\) using equation (II) we have since n is odd the reminder would be 7-1 =6
\(\frac{21^{875}}{17}\) = we can split this as \(\frac{(17*1+4)^{875}}{17}\) remainder will be given by the part \(\frac{(4)^{875}}{17}\) that is \(\frac{(4^2)^{437} (4) }{17}\) = remainder will be given by \(\frac{4}{17}\) using equation (II) we have since n is odd the reminder will be 4
\(\frac{54^{124}}{17}\) = we can split this as \(\frac{(17*3+3)^{124}}{17}\) so reminder will be given by the part\(3^{124}\) , = \(\frac{(3)^{124}}{17}\)we can split this as\(\frac{(3^4)^{31}}{17}\) which is \(\frac{(81)^{31}}{17}\) we can split this as \(\frac{(17*5-4)^{31}}{17}\). so reminder will be given by the part -\((4)^{31}\) we can split this as \(\frac{-(4^2)^{15} (4)}{17}\). remainder will be given by the part \(\frac{-(16)^{15} (4)}{17}\)= \(\frac{-(-1)^{15} (4)}{17}\) = \(\frac{-(-1)^{15} (4)}{17}\) , so reminder is 4
\(\frac{83^{261}}{17}\) = we can split this as \(\frac{(17*5-2)^{261}}{17}\) , reminder would be given by the part \((-2)^{261}\) which is same as - (2)^{261} then \(\frac{-(2)^{261}}{17}\) can also be written as \(\frac{-(2^4)^{65} * 2 }{17}\) = \(\frac{-(16)^{65} * 2 }{17}\)=
\(\frac{-(-1)^{65} * 2 }{17}\) = \(\frac{-(-1) * 2 }{17}\) = \(\frac{2}{17}\) reminder would be 2
\(\frac{25^{102}}{17}\) = we can split this as \(\frac{(17*1+8)^{102}}{17}\) reminder would be given by the part \(\frac{(8)^{102}}{17}\) which is same as \(\frac{(2^4)^{76}(2^2)}{17}\), which would give reminder as 4
Hope this helps