This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Actually, the 1 2 3 4 5 6 ( m o d 1 2 5 ) is where it gets interesting. It could be very painful, or it could be a pleasant breeze.
Hint: The numbers were not randomly chosen, despite appearances.
Log in to reply
By Euler, this simplifies to 1 2 3 5 6 ≡ ( − 2 ) 5 6 ≡ ( 1 2 8 ) 8 ≡ 3 8 and from here it is easy.
Log in to reply
Precisely! For those who didn't notice that 1 2 3 ≡ − 2 , this problem became painful. Likewise, 5 6 = 7 × 8 , 2 7 = 1 2 8 would simplify the working further. Thanks for sharing!
BTW I'm hosting a wiki collaboration party on Finding the last few digits of a power this Saturday at 8am PDT. Would you be able to contribute?
@Calvin Lin , I used Eulers theorem as we know totient of 1000 is 400 , the above number gets reduced to 1 2 3 5 6 modulo 1000 and then some calculations , it gets bit tedious too ...Please do reply for this method...
Log in to reply
As stated in my comment "It could be very painful, or it could be a pleasant breeze".
You chose the painful approach. See Alan's solution for the pleasant breeze.
@Calvin Lin the last digit of 1 2 3 4 5 6 will return 3 6 = 7 2 9 as 9.
What is ϕ in your solution?
1 2 3 4 5 6 ≡ ( 1 2 3 2 ) 2 2 8 ≡ 1 2 9 2 2 8 ≡ ( 1 3 0 − 1 ) 2 2 8 ≡ 1 3 0 2 × ( 2 2 2 8 ) − 1 3 0 × 2 2 8 + 1 ≡ 5 6 1 ( m o d 1 0 0 0 )
123^2=129. hahaha. what a coincidence ans is same
Log in to reply
@Vibhor Chandak How 1 2 3 2 = 1 2 9 ?
It is ( 1 0 0 + 2 3 ) 2 = 1 0 0 2 + 2 × 1 0 0 × 2 3 + 2 3 2 = 1 0 0 0 0 + 4 6 0 0 + 5 2 9 = 1 5 1 2 9 .
Not 1 2 9 .
x = 1 2 3 4 5 6 We want to find x in modulo 1000.
Since ϕ ( 8 ) = 4 , we know that x ≡ 1 (mod 4) Since ϕ ( 1 2 5 ) = 1 0 0 , we know that x ≡ 6 1 (mod 125) (Calculations left to reader however it is very helpful to consider 123 as -2)
Using the chinese remainder theorem, we get that x ≡ 5 6 1 (mod 1000) therefore yielding an answer of 5 6 1 .