<s>[INST] Proving $5 \mid (n^5-n)$ for all $n \in \mathbb{Z}^+$ 
Prove for all $n \in \mathbb{Z}^+$ that $5 \mid (n^5-n)$ 

My proof
Basis step: Since $5 \mid (1^5-1) \iff 5 \mid 0$ and $5 \mid 0$ is true, the statement is true for $n=1$.
Inductive step: Assume the statement is true for $n = k$; that is, assume that  $5 \mid (k^5-k)$ is true. Then there is $m \in \mathbb{Z}^+$ such that $$k^5 - k = 5m.$$ We must show that this statement is true for $n = k+1$, i.e. show that there is $\ell \in \mathbb{Z}^+$ such that $$(k+1)^5 - (k+1) = 5\ell.$$ Note that $(k+1)^5 - (k+1)$ expands as $k^5 + 5k^4 + 10k^3 + 10k^2 + 4k$.
We can try to find a polynomial $P(x)$ such that $$(k^5-5) + P(x) =(k+1)^5 - (k+1) = k^5 + 5k^4 + 10k^3 + 10k^2 + 4k$$ so as to try to add $P(x)$ to both sides of the assumption. We find that 
$$\begin{align}P(x) &=  k^5 + 5k^4 + 10k^3 + 10k^2 + 4k - (k^5-5) \\
&=5k^4 + 10k^3 + 10k^2 + 5k  \end{align}$$ and we can also observe that since $k\in\mathbb{Z}^+$, we have that $\frac{1}{5}P(x) = k^4 + 2k^3 + 2k^2 + k$ is a positive integer. Thus we add this to both sides of our assumption $$ \begin{align}
k^5 - k &= 5m \\
(k^2 - k) + P(x) &= 5m + P(x) \\
(k+1)^5 - (k+1) &= 5\left(m + \tfrac{1}{5}P(x)\right)
\end{align}.$$ Since $\frac{1}{5}P(x),m \in \mathbb{Z}^+$, it follows that $m + \tfrac{1}{5}P(x) \in \mathbb{Z}^+$. Thus $5 \left| \big[ (k+1)^5 - (k+1) \big] \right.$
By PMI,  $5 \mid (n^5-n)$ for all $n \in \mathbb{Z}^+$.
My questions


*

*Is this proof valid?

*What other ways can this be proved by induction? The polynomial expansions took a while to deal with, so I was wondering if there are any alternate methods. (Just FYI, I only have college first-year-level knowledge)

 [/INST] $n^5 - n = n(n^4 - 1) = n(n^2 - 1)(n^2 + 1) = n(n - 1)(n+1)(n^2 + 1)$.
There is a unique $q, r$ so that $n = 5q + r; 0\le r < 5$. This is basically dividing $n$ by $5$ and finding the remainder.
If $r = 0$ then $n = 5q$ and $n^5 - n = 5q(n-1)(n+1)(n^2 + 1)$ and we are done.
If $r = 1$ then $n = 5q +1$ and $n-1 = 5q$ and $n^5 -n = n(5q)(n+1)(n^2 + 1)$ and we are done.
If $r = 2$ then $n = 5q + 2$ and $n^2 + 1 = (5q+2)^2 + 1 = 25q^2 + 20q + 4 + 1 = 5(5q^2 + rq + 1)$ and $n^5 -n = n(n-1)(n+1)5(q^2 + 4q + 1)$ and we are done.
If $r = 3$ then $n = 5q + 3$ and $n^2 + 1 = (25q^2 + 30q + 9) + 1 = 5(q^2 + 6q + 2)$ and  $n^5 -n = n(n-1)(n+1)5(q^2 + 6q + 2)$ and we are done.
If $r = 4$ then $n = 5q + 5$ and $n + 1 = 5q +5=5(q+1)$ and $n^5 - n = n(n-1)5(q+1)(n^2 + 1)$ and we are done.
Those are the only $5$ options.
</s>