@[361226:ayushbhalotia]
See, its not a thumb rule that u solve every Remainder Qn by Euler's.
The efficient way to solve this Qn should be to use Chinese Remainder Theorem(CRT) along with Euler's Theorem
How do you decide that Euler alone wont be profitable here.
Lets see..
Since 3 and 77 do not have any factor in common, so we can use Euler's Theorem here.
So, calculate Euler function of 77.
77=7*11
Euler of 77 = E(77) = 77*( 1-1/7)*(1-1/11) = 60.
So now we have determined that Rem[ (3^60)/77 ] = 1
Our Qn becomes Rem[ (3^101)/77 ] = Rem[ (3^41)/77 ]
Now you will find urself stuck here. 77 is too big a number to play around with, calculating its powers while taking any exam will waste time.
So we should employ CRT here.
But still, in case you you cannot recall CRT you can continue the above reduction to arrive at the answer.
Rem[ (3^41)/77 ] = R [ ( (81^10).3 )/77 ]
= R[ ( (4^10).3 )/77 ] ......................... { 81 = 77 + 4 }
= R[ ( (64^3).4.3 )/77]
= R[ ((-13)^3).12)/77 ] ......................... { 64 = 77-13 }
= R[ ( (169)(-13)(12) )/77 ]
= R[ ( (15)(-13)(12) )/77 ] .....................Since { 169=77*2+15 }
= R[ ( (-15)(156) )/77 ]
= R[ ( (-15)(2) )/77 ]......................Since { 156=77*2+2 }
=R[ (-30)/77 ]
=77-30 = 47 ...........Answer
**********************************
Now see how CRT makes our life easier.
STEP1:
We have to find REM[ (3^101)/77 ].
Note here that 77=7*11
So , we calculate remainder of 3^101 by both the factors of 77.
REM[ 3^101 / 11 ] = 3 ........................{ Euler(11) = 10, R[3^100/11] = 1 }
REM[ 3^101/ 7 ] = R[ 3^5/7 ] .....................{ Euler(7) = 6 , R[ 3^96/7 ] = 1 }
= R[ ( (9)(9)(3) )/7]
=R[ ( (2)(2)(3) )/7 ] = R[ 12/7 ] = 5 .
STEP2:
As per CRT, we have to find values of x and y such that
7x + 11y = 1
One such pair is x=-3 y=2
STEP3:
Desired Remainder =
7(Remainder from divisn by 11)(value of x) + 11(Remainder from divisn by 7)(Value of y)
= (7)(3)((-3) + (11)(5)(2)
= - 63 + 110
= 47...........Answer
Whooossshh,, That was a pretty long post.
Hope u can understand,
Bounce back in case of any doubt.
Never Back Down