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$...
$\endgroup$ 31 Answer
$\begingroup$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}$.
$\endgroup$
