How many integers a from 1 to 1000 are there such that $a^{100}-1$ is divisible by 1000?
I need to find how many $a$ there are such that $a^{100}\equiv 1\pmod{8}$ and $a^{100}\equiv 1\pmod{125}$, but I don't know how to go on from here. Could I get some help? Thanks!
First solution: $\lambda(1000)=100$. so $a^{100}\equiv 1$ for all $a$ with $(a,1000)=1$. there are $\varphi(1000)=400$ such numbers.
Second solution:
$\varphi(8)=4$, so by Euler's theorem all $a^{100}=(a^{4})^{25}\equiv 1 \bmod 8$ for all odd numbers.
$\varphi(125)=100$, so all numbers that are not multiples of five satisfy $a^{125}\equiv 1$ by Euler.
Therefore you want numbers coprime to $1000$. There are $\varphi(1000)=400$.