Show that $30 \mid (n^9 - n)$ 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.
 A: 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}$
A: 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$
A: 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$

A: 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
A: 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)$
