# 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!

• Well, $n^k \equiv n \pmod{\gcd(30,n)}$ for every $k > 0$. So it remains to consider $$n^9 \equiv n \pmod{\frac{30}{\gcd(30,n)}}.$$ – Daniel Fischer Oct 26 '13 at 23:44
• When is the $gcd(30,n)>1$ and we also know $0\leq n <30$. So we know when $n=2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28$ but what divides $30$ out of these numbers? – user60887 Oct 26 '13 at 23:53
• 2, 3, 5, 6, 10, 15 divides 30 out of those numbers listed, is there an easy conclusion that $n^9 \equiv n \pmod{30}$ out of those numbers without considering that these are all multiples of the primes 2,3,5 and using Fermat? :) – Numbersandsoon Oct 26 '13 at 23:56

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$.
• Shouldn't it be $n^{p}\equiv n \pmod p$? – Numbersandsoon Oct 27 '13 at 0:09
• That too is true. But since $p-1$ divides $8$ for $p=2,3,5$, we have $n^8\equiv 1 \pmod{p}$ whenever $n$ is not divisible by $p$, and therefore $n^9\equiv n\pmod{p}$. – André Nicolas Oct 27 '13 at 0:39
Notice that $30 = 2\cdot3\cdot5$, so $(30, n) = (30, n^9)$. Then it is enough to show that $n^9 \equiv n \pmod{\frac{30}{(30, n)}}$. It follows from what you already have taking into account that $(n, \frac{30}{(30, n)}) = 1$ and $\varphi(d) \mid \varphi(m)$ for any $d\mid m$.
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.