$a^{100}-1$ is divisible by $1000$.

Question

While working on competition math, I came upon the following problem: How many integers $x$ from $1$ to $1000$ are there such that $x^{100}-1$ is divisible by $1000$? This was very confusing, as the numbers that I had to deal with were so large, so I thought of using mods. Here is what I did: $$\begin{array}{l} x^{100}-1\equiv 0 \mod 1000\\ x^{100}\equiv 1 \mod 1000 \end{array} $$ From this, we are basically trying to find number of $x$'s such that $x^{100}$ ends in $0001$. How should I proceed to solve this?

Answer 1

By the Chinese remainder theorem, the solutions of $x^{100} \equiv 1 \bmod 1000$ are exactly the solutions of the system $$ x^{100} \equiv 1 \bmod 8, \qquad x^{100} \equiv 1 \bmod 125 $$ Now, $100$ is a multiple of both $\phi(8)=4$ and $\phi(125)=100$ and so all numbers that are coprime with both $8$ and $125$ are solutions of this system.

Therefore, the solutions of $x^{100} \equiv 1 \bmod 1000$ are exactly the numbers coprime with $1000$. There are $\phi(1000)=400$ solutions in $[1,1000]$.