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.