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)

 A: You were close to a shorter proof after you expanded $(k+5)^5-(k+1)$, since
\begin{align*}
(k+5)^5 - (k+1) &= k^5 + 5k^4 + 10k^3 + 10k^2 + 4k \\
&= (k^5-k) + (5k^4 + 10k^3 + 10k^2 + 5k),
\end{align*}
and by induction hypothesis, $5$ divides $k^5-k$ and clearly $5$ divides each term in $5k^4 + 10k^3 + 10k^2 + 5k$, so $5$ divides $(k+5)^5 - (k+1)$. The moral of the story is that sometimes it's a good idea not to cancel things out, but to try to find a way to shift them around.

Edit: I see this is effectively what you ended up with anyway, but finding ways to shorten proofs and make them clearer is a good thing to strive for.
A: In $\mathbb{Z}_5$ the integers mod $5$, which is a field, all elements obey $x^5=x$, or $0= x^5 -x$, from which the statement follows right away. 
A: An alternative proof: 
Note that we can write $n^{5} - n$ as follows:
$$n^{5} - n = 5\left[6{n\choose 2} + 30{n\choose 3} + 48{n\choose 4} + 24{n\choose 5}\right].$$
This is very clearly a multiple of $5$ (the expression is $5$ times another integer), so we are done.
Here, ${n\choose k} = {\frac{n!}{k! (n-k)!}}$
A: Here is another way. For every $n \in \mathbb{Z}^{+}$, we have
(here we use $a^2 -b^2 = (a-b)(a+b)$)
\begin{align}
n^5 - n = n(n^4 -1) & = n(n^2-1)(n^2+1) \\
&= n(n-1)(n+1)(n^2 -4 +5) \\
& = n(n-1)(n+1)(n^2 -4) + 5n(n-1)(n+1) \\
& = n(n-1)(n+1)(n-2)(n+2) + 5n(n-1)(n+1) \\
& = (n-2)(n-1)n(n+1)(n+2) + 5n(n-1)(n+1).
\end{align}
In the last line, the first term is a product of 5 consecutive
integers, so it must be divisible by $5$. Moreover, clearly $5$ divides the second one :)
A: $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.
