Does $30$ divide $n^5-n$ for all positive integers $n$?
  1. Factorise $n^2-2n-3$.
  2. Is $n^2+n$ always even when $n$ is an integer?
  3. Does $6$ divide $100002$? Try to reason about the divisors of both numbers.

How do you split $30$ into a product of prime factors?

Can you factorise $n^5 - n$?

You should obtain $n(n-1)(n+1)(n^2+1)$. What can you say about the product of 3 consecutive numbers in terms of divisibility by $2$ and $3$?

If you assume that $5$ divides $n^5-n$, how can you prove that 5 divides $(n+1)^5-(n+1)$?

First notice that $30=2\cdot3\cdot5$. Since $2$, $3$ and $5$ are all coprime we will prove that each of them divides $n^5-n$ and hence conclude that their product does too. We now factorise $n^5-n$: $$ \begin{aligned} n^5-n &= n(n^4-1) \\ &= n(n^2-1)(n^2+1)\\ &= n(n-1)(n+1)(n^2+1) \end{aligned} $$ The product $(n-1)n(n+1)$ is of 3 consecutive numbers, hence necessarily both 2 and 3 must divide it. We must now prove divisibility by $5$. There are several approaches to do this, but here we shall use induction. It’s easy to verify the base case for $n=0$ or $n=1$. Then do the inductive step: $$ \begin{aligned} (n+1)^5 - (n+1) &= n^5 + 5n^4 + 10n^3 + 10n^2 + 5n - n \\ &= n^5-n + 5(n^4+2n^3+2n^2+n) \end{aligned} $$ First part is divisible by $5$ owing to the induction hypothesis, while the rest is obviously a multiple of 5.