Show that $30 \mid (n^9 - n)$

Question

I am trying to show that $30 \mid (n^9 - n)$. I thought about using induction but I'm stuck at the induction step.

Base Case: $n = 1 \implies 1^ 9 - 1 = 0$ and $30 \mid 0$.

Induction Step: Assuming $30 \mid k^9 - k$ for some $k \in \mathbb{N}$, we have $(k+1)^9 - (k+1) = [9k^8 + 36k^7 + 84k^6 + 126k^5 + 126k^4 + 84k^3 + 36k^2 + 9k] - (k+1)$.

However I'm not sure where to go from here.

Answer 1

And here are the congruences requested to complement the answer by Simon S

$$\begin{array}{c|ccccc} n&n-1&n+1&n^2+1&n^4+1\\ \hline 0&4&1&1&1\\ 1&0&2&2&2\\ 2&1&3&0&4\\ 3&2&4&0&2\\ 4&3&0&2&2 \end{array}$$

And one can see that one of these factors is always $\equiv 0\pmod{5}$

Answer 2

Hint: Note that

$$n^9 - n = n(n^8 - 1) = n(n-1)(n+1)(n^2+1)(n^4+1)$$

This expression is equal to zero mod $2$ and mod $3$, as $n-1, n, n+1$ are factors.

If you can show that at least one of these factors is divisible by $5$ you'll be done, as $2|m, 3|m, 5|m \Rightarrow 30|m$.

There are just five cases to consider $n \equiv 0,1,2,3,4 \mod 5$. For example

• if $n \equiv 0$ then the factor $n \equiv 0$
• if $n \equiv 1$ then the factor $n-1 \equiv 0$
• if $n \equiv 2$ then the factor $n^2 + 1 \equiv 0$

Answer 3

Well, $30=2.3.5$ so only is necesary proof that $2,3,5 \mid (n^9 - n)$ is easy see that $2\mid (n^9 - n)$, next using that $ n^3 = \,n \,mod \,3$ you get that $3\mid (n^9 - n)$ at the end using that $n^4 = \,1 \,mod \,5$ and $n^5 = n \,mod \,5$ get that $5 \mid (n^9 - n)$ and finish the proof. the best

Answer 4

Carmichael's function $\lambda(30)=4$, since $4=lcm(\phi(2),\phi(3),\phi(5))$.

So for all $b\ge 1$, $a^{b+4} \equiv a^b \bmod 30$. In particular $a^9\equiv a^5\equiv a \bmod 30$, so $(a^9-a) \equiv 0 \bmod 30$, giving $30 \mid (a^9-a)$

Answer 5

Here's an alternative way of doing it: Since $\phi(30)=8$, we get that $m^9 \equiv m \pmod{30}$ whenever $(m,30)=1$. Since the only factors of $30$ are $2$,$3$, and $5$, we write: $$ n=2^a \cdot 3^b \cdot 5^c \cdot m$$ Where $(m,30)=1$. Now: $$ n^9 = 2^{9a} \cdot 3^{9b}\cdot 5^{9c} \cdot m^9 \equiv (2^9)^a \cdot (3^9)^b \cdot (5^9)^c \cdot m \pmod{30}$$ Now note: $$2^9 \equiv 2 \pmod{30}$$ $$3^9 \equiv 3 \pmod{30}$$ $$5^9 \equiv 5 \pmod{30}$$ So therefore: $$n^9 \equiv 2^a \cdot 3^b \cdot 5^c \cdot m \equiv n \pmod{30}$$ And therefore $30 \mid n^9-n$