# Why is $x^{100} = 1 \mod 1000$ if $x < 1000$ and $\gcd (x,1000) = 1$?

Let $U(1000) =$ the multiplicative group of all integers less than and relative prime to $1000$.

"Show that for every $x \in U(1000)$ it is true that $x^{100} = 1 \mod 1000$."

Been thinking about this for hours but I cannot for the life of me find out why this is true.

My intuition is that is has something to do with Euler's Theorem: $a ^{\varphi (n)} \equiv 1 (\mod n)$, but $\varphi(1000) = 400$, not $100$...

• Have you heard of the Carmichael function? Also, think of the Chinese remainder theorem. – Daniel Fischer Jun 27 '15 at 11:52
• To add to what @DanielFischer wrote: think of $x^{100}$ modulo $8$ and modulo $125$, then combine the two. – Rory Daulton Jun 27 '15 at 11:55
• Thank you all for the helpful comments and the editing of my post with a better presentation. Much appreciated :) – Tim Strijdhorst Jun 27 '15 at 13:20

To check that $x^{100} - 1$ is divisible by $1000$, it will suffice to check that it is divisible by $8$ and $125$. For each of these, you can use Euler's theorem, which will tell you that $x^{p^{k-1}(p-1)} \equiv 1 \pmod {p^k}$, where $p$ is a prime not dividing $x$. In this particular case, you have $x^{4} \equiv 1 \pmod{8}$ (so in particular $x^{100} \equiv 1 \pmod{8}$) and $x^{100} \equiv 1 \pmod{125}$.