Prove that $n^9 \equiv n \pmod{30}$ if $(30,n) > 1$ I'm looking at the following number theory problem:
Prove that $n^9 \equiv n \pmod{30}$ for all positive integers $n$ if $(30,n) > 1$.
It is easy to show that $n^9 \equiv n \pmod{30}$ if $(30,n)=1$ by using Euler's Theorem. Is there any way to prove the above easily when $(30,n)$ are not relatively prime? I'm looking for some easy realization, and not factoring $n^9-n=n(n^8-1)=n(n^4+1)(n^4-1)=n(n^4+1)(n^2+1)(n-1)(n+1)$ and then deducing divisibility. Is there a simple realization for this?
Thanks!

You know that $n^9-n=0\mod 30$ if, and only if $n^9-n=0\mod 2$, $n^9-n=0\mod 3$ and $n^9-n=0\mod 5$. But modulo $2$; we have $n^2=n$, so $n^9=n$ immediately. If $n\neq 0$, $n^2= 1$ modulo $3$, so $n^3=n$, so $n^9=n^3=n$ so $n^9=n$. Modulo $5$, if $n\neq 0$, $n^2=\pm 1$ so $n^4=1$ so $n^5=n$ so $n^9=n^5n^4=n^5=n$ and the proof is finished.
