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?
Asked
Active
Viewed 1,272 times
1 Answers
4
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]$.
lhf
- 216,483
-
Wow! Thanks, I didn't think of using the CR, but I guess it helps to simplify this a lot! – RK01 May 06 '16 at 02:50
-
1@RK01, note how Euler's theorem does not help for $1000$. You need Carmichael's $\lambda$ function instead of Euler $\phi$. – lhf May 06 '16 at 02:53