[Math] Show that $30 \mid (n^9 – n)$

divisibilityelementary-number-theoryinduction

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

  • 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$
Related Question