Prove $(n^5-n)$ is divisible by 5 by induction.

Solution 1:

Your induction hypothesis is that $5\mid k^5-k$, which means that $k^5-k=5n$ for some integer $n$. Now

$$\begin{align*} (k+1)^5-(k+1)&=\left(k^5+5k^4+10k^3+10k^2+5k+1\right)-(k+1)\\ &=k^5+5k^4+10k^3+10k^2+5k-k\\ &=(k^5-k)+5k^4+10k^3+10k^2+5k \end{align*}$$

can you see why that must be a multiple of $5$?

Solution 2:

Hint $\ \ n^5\!-\!n = n(n^2\!-\!1)(n^2\!-\!4\! +\! 5) = (n\!-\!2)(n\!-\!1)n(n\!+\!1)(n\!+\!2)+ 5n(n^2\!-\!1)$

Thus it suffices to show that $\,5\,$ divides a product of $\,5\,$ consecutive integers. In fact, any sequence of $\,n\,$ consecutive naturals has an element divisible by $\,n\,$. This has a simple proof by induction: shifting such a sequence by one does not change its set of remainders mod $\,n,\,$ since it effectively replaces the old least element $\:\color{#C00}a\:$ by the new greatest element $\:\color{#C00}{a+n}$

$$\begin{array}{}& \color{#C00}a, &\!\!\!\! a+1, &\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1 & \\ \to & &\!\!\!\! a+1,&\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1, &\!\!\!\! \color{#C00}{a+n} \end{array}\qquad$$

Since $\: \color{#C00}{a\,\equiv\, a\!+\!n}\pmod n,\:$ the shift does not change the remainders in the sequence. Thus the remainders are the same as the base case $\ 0,1,2,\ldots,n-1\ =\: $ all $ $ possible remainders mod $\,n.\,$ Therefore the sequence has an element with remainder $\,0,\,$ i.e. an element divisible by $\,n.$