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.
Best Answer
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