Originally Posted by
kiddopop Question: What are the last three digits of x=673^(2802) when it is written base 10? (Hint: This is the same as asking for the remainder when x is divded by 1000)
I figured it out, just wanted to make sure this was right...
1000=2^3 x 5^3
ϕ(1000)=2^2(2-1) x 5^2(5-1)
=4 x 1 x 25 x 4 = 400
ϕ(1000)=400
Using Euler's Theorem
gcd(673, 1000) = 1 so 673^400≡1(mod 1000)
2802=400 x 7 + 2 so, the original x can be written x=(673^400)^7 x 673^2.
Since we know that 673^400≡1 we can write x=1^7 x 673^2.
We have 1^7 x 673^2 ≡ 673^2 (mod 1000) ≡ 452929 ≡ 929(mod 1000)
The remainder when x=673^2902 is divided by 1000 is 929, so the last three digits of x when it is written in base 10 is 929.