SOLUTION: Find the remainder 23^(300)%40 that is left when 23^(300) is divided by 40

Algebra ->  Distributive-associative-commutative-properties -> SOLUTION: Find the remainder 23^(300)%40 that is left when 23^(300) is divided by 40      Log On


   

Question 27146: Find the remainder 23^(300)%40 that is left when 23^(300) is divided by 40
Answer by kev82(151) About Me  (Show Source):
You can put this solution on YOUR website!
Hi,
This is quite easy if you know how. The first thing you need to know is the identity.

If your not comfortable with this then try proving it. This identity means we can take the remainder at any time during the multiplication without effecting the result.
We could quite naivly proceed to evalute given . That would take you ages though so I'm going to do some repeated squaring. Google for 'repeated squaring' if you want more information.
x%5E300=%28x%5E150%29%5E2
x%5E150=%28x%5E75%29%5E2
x%5E75=x%2Ax%5E74
x%5E74=%28x%5E37%29%5E2
x%5E37=x%2Ax%5E36
x%5E36=%28x%5E18%29%5E2
x%5E18=%28x%5E9%29%5E2
x%5E9=x%2Ax%5E8
x%5E8=%28x%5E4%29%5E2
x%5E4=%28x%5E2%29%5E2
I'm going to take modulus 40 after every multiplication. Subbing x=23 into this (from bottom up) gives.
x%5E2=9
x%5E4=1
x%5E8=1
x%5E9=23
x%5E18=9
x%5E36=1
x%5E37=23
x%5E74=9
x%5E75=7
x%5E150=9
x%5E300=1
So there ya go.
Hope that helps,
Kev