number theory - Prove that $7^{100} - 3^{100}$ is divisible by $1000$

Prove that $7^{100} - 3^{100}$ is divisible by $1000$

Equivalently, we want to show that $$7^{100} = 3^{100} \pmod {1000}$$

I used WolframAlpha (not sure if that's the right way though) and found that $\varphi (250) = 100$.

So by Euler's theorem: $$7^{100} \equiv 7^{\varphi(250)} \equiv 1 \pmod {250} \\ 3^{100} \equiv 3^{\varphi(250)} \equiv 1 \pmod {250}$$

but of course, we want $\pmod {1000}$.

Is that what I'm intended to do in this exercise (how to proceed if so)? Is there a solution without the need to use WolframAlpha?

Thanks!

Answer

Wolfie A is never the right way.

By the Chinese remainder theorem, all you need is to prove both
$$7^{100}\equiv3^{100}\pmod8$$ and

$$7^{100}\equiv3^{100}\pmod{125}.$$
You have already done the latter. But $7^2\equiv1\pmod 8$
and $3^2\equiv1\pmod 8$ so it's a fair bet that $7^{100}\equiv3^{100}
\pmod8$ too.