Prove that if $n$ is coprime to $10$ then $n^{101} \equiv n \pmod{1000}$

Question

"Prove that if $n$ is coprime to $10$ then $n^{101} \equiv n \pmod{1000}$"

I know that this has something to do with Euler's function, but i'm not sure how to apply it.

A fellow on an IRC channel that I am on answered this question, but I did not understand his process. Written below is his process.

---

"$n$ is prime to $10$ => $n^{\phi(125)+1} = n^{101} = n \pmod{125}$

since $n^2 = 1 \pmod{8}, n^{50*2+1} = n^{101} = n \pmod{8}$ => $n^{101} = n\pmod{125 * 8}$; Thus if $gcd(n,10)=1$ then $n^{101} = n \pmod{1000}$"

---

If $n$ is coprime to $10$, why are we allowed to say $n^{\phi(125)+1}$? Eueler's function says if $n$ and $a$ are coprime, then: $a^{\phi(n)} \equiv 1 \pmod{n}$.

I think I just need this part explained and i'll be okay.

Answer 1

Euler's theorem tells us $n^{\varphi(125)}\equiv 1\pmod{125}$. Multiplying both sides by $n$ yields $n^{\varphi(125)+1}\equiv n\pmod{125}$. As you can tell, $\varphi(125)=\varphi(5^3)=5^2(5-1)=100$. So far we have:$$n^{100+1}\equiv n\pmod{125}\\n^{101}\equiv n\pmod{125}$$Can you finish the rest? Because $n$ is coprime to $10$ it follows that it is also coprime to $2,5$ and also any of their powers -- which is how we knew $n$ and $5^3=125$ were coprime. You can use a similar argument for $n$ and $2^3=8$.

Answer 2

We can use Carmichael function,

$\lambda(1000)=$lcm$(\lambda(5^3),\lambda(2^3))=$lcm $(100,2)=100$

---

Alternatively, as $n^{100}\equiv1\pmod{125}$

and as $n$ is odd, $n^2=(2m+1)^2=8\frac{m(m+1)}2+1\equiv1\pmod 8$

$\implies n^{lcm(100,2)}\equiv1\pmod {125}$ and $n^{lcm(100,2)}\equiv1\pmod 8$

$\implies n^{100}\equiv1\pmod {125}$ and $n^{100}\equiv1\pmod 8$

$\implies n^{100}-1 $ will be divisible by lcm$(125,8)=1000$

This is what is hidden in Carmichael function