2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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)}}.$$ $\endgroup$ – Daniel Fischer Oct 26 '13 at 23:44
  • $\begingroup$ 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? $\endgroup$ – user60887 Oct 26 '13 at 23:53
  • $\begingroup$ 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? :) $\endgroup$ – Numbersandsoon Oct 26 '13 at 23:56
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Shouldn't it be $n^{p}\equiv n \pmod p$? $\endgroup$ – Numbersandsoon Oct 27 '13 at 0:09
  • 1
    $\begingroup$ 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}$. $\endgroup$ – André Nicolas Oct 27 '13 at 0:39
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.