<s>[INST] How to prove $n^5 - n$ is divisible by $30$ without reduction How can I prove that prove $n^5 - n$ is divisible by $30$?
I took $n^5 - n$ and got $n(n-1)(n+1)(n^2+1)$
Now, $n(n-1)(n+1)$ is divisible by $6$.
Next I need to show that $n(n-1)(n+1)(n^2+1)$ is divisible by $5$.
My guess is using Fermat's little theorem but I don't know how.
 [/INST] It suffices to show that $k^5-k$ is always divisible by each of 2, 3, and 5.  That is, we want $k^5-k\equiv 0 \mod d$ where $d$ is each of 2, 3, and 5.
We know that $k\equiv r\pmod 2$ where $r$ is 0 or 1.  Then $k^5 - k  \equiv r^5-r \equiv 0 \pmod2$. The last equivalence follows instantly from a consideration of the two cases: either $r=0$ in which case we have $0^5-0\equiv 0\pmod 2$, or $r=1$ in which case we  have $1^5-1\equiv 0\pmod 2$.
Similarly $k\equiv r\pmod 3$ where $r$ is one of 0, 1 or 2.  In each case consider $r^5-r\pmod 3$.  The first two cases are completely trivial, and the same as in the previous paragraph. The $r=2$ case gives $32-2= 30\equiv 0\pmod 3$.
And again $k\equiv r\pmod 5$ where $r$ is one of $\{0,1,2,3,4\}$; now consider $r^r-r\pmod 5$.  Again cases 0 and 1 are trivial; the other three give $30\equiv 0\pmod 5$, $3^5-3 = 243-3 = 240\equiv 0\pmod 5$, and $4^5-4 = 1024-4 = 1020 \equiv 0\pmod 5$, so we are done.
</s>