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.

Funny brute force approach. Just show:
$$n^5-n = 5!\binom{n+2}{5} + 5\cdot 3!\binom{n+1}{3}=120\binom{n+2}{5}+30\binom{n+1}{3}$$
In general, if $d$ is odd, then you can write:
$$n^d-n = \sum_{i=0}^{\lfloor d/2\rfloor} a_i \binom{n+i}{2i+1}$$
where the $a_i$ are multiples of $(2i+1)!$.
Since the left side is divisible by $(n+1)n(n-1)$, we have that $a_0=0$. We also have $a_{\lfloor d/2\rfloor}=1$. So we have $\lfloor d/2\rfloor-1$ different $a_i$ to determine.
But you can actually determine them by induction, since $\binom{n+i}{2i+1}=0$ when $2i+1>n$. So choose $n=2$ and we get $2^{d}-2 = a_1\binom{3}{3}$ so $a_1=(2^{d}-2)$.
Then take $n=3$, and we get:
$$3^d-3 = a_2\binom{3+2}{5} + a_1\binom{3+1}{3}=a_2 + 4(2^d-2)$$
So $a_2 = 3^d-3 - 4(2^d-2)$.
In general, for $a_k$, we take $n=k+1$ and:
$$a_k = (k+1)^d - (k+1) - \sum_{i=0}^{k-1} a_i\binom{k+1+i}{2i+1}$$
By induction, you can prove that if $D\mid n^d-n$ for all integers $n$, then $D$ must divide $a_i$ for all $i$. And obviously, any factor of all $a_i$ is a common factor of $n^d-n$ for all $n$. So the general solution is the greatest common divisor of $a_1,\dots,a_{\lfloor d/2\rfloor}$. You can do this sequentially, so you compute $3^d-3$ modulo $2^d-2$, and then compute the GCD, etc.
For example, for $d=7$, $2^7-2=126$. Next compute $3^7-3\bmod {126}=42$. Since $42\mid 126$, we get $\gcd(2^7-2,3^7-3)=42$. Then compute $4^7-4$. This is actually obviously divisible by $2(2^6-1)=a_1$. So we get:
$$\gcd(2^7-2,3^7-3,4^7-4)=42$$
This actually works with any odd integer polynomial $g(n)$ of degree $d$ - the greatest common factor of the values of $g(n)$ is:
$$\gcd(g(1),g(2),\dots,g(\lceil d/2\rceil))$$
Now, if $a^d\equiv a\pmod D$ and $b^d\equiv b\pmod D$ then $(ab)^d \equiv ab\pmod{D}$. So $g(n)=n^d-n$ has the particular property that if $D\mid g(a)$ and $D\mid g(b)$ then $d\mid g(ab)$. So you only have to compute the cases in the set where $n$ is prime. So, for example, when $d=19$, you get:
$$\gcd(2^{19}-2,3^{19}-3,5^{19}-5,7^{19}-7)$$

This has all eschewed using Fermat, only using some divisibility theorems and knowledge about binomials and congruences.Indeed, the above argument
But with Fermat's little theorem, we can get much further.
It's pretty obvious that $D$ has to be square-free, because for any prime $p$, $p^d-p$ has only one factor of $p$.
Also, if $n^d-n$ is divisible by $p$ for all $n$ then for any if $g$ is a generator modulo $p$, then $g^d\equiv g\pmod p$ means that $p-1$ divides $d-1$. And visa versa, if $p-1\mid d-1$, then $p$ is a common factor.
So what this really means is that the greatest common factor of $n^d-n$ with $d$ odd is exactly the product of the primes $p$ such that $p-1\mid d-1$.
The same argument works for $d$ even, so that the common factor of $n^d-n$ when $d$ is even is always just $2$, since for any odd prime $p$, $p-1$ is not a factor of the odd $d-1$.
