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!

If $p$ is one of $2,3,5$ then $n^9\equiv n\pmod{p}$. This is true by Fermat's Theorem if $n$ and $p$ are relatively prime, and trivially true if $p$ divides $n$.
