How to reason that $n^5 - n$ is divisible by 2 as proof for a consequence of Fermat's little theorem. In my text book on Discrete Mathematics (I), we have a chapter that covers a bit of elementary Number Theory. In it we see the famous Theorem of Euler as well as the derived little theorem of Fermat. I understand these theorems and even the proofs that are given for them in my text book. There is however a specific step in the proof given for Fermat's little theorem that I do not understand. For the sake of completeness I'll write both the resulting theorem (derived from Fermat's little theorem) and its proof here as written in my text book.
$$
\forall n \in \mathbb N^* : n \text{ and } n^5 \text{ always end on the same digit.}
$$
The proof goes as follows.
Because Fermat's little theorem we know that
$$
\begin{equation}
\begin{aligned}
n^5 &\equiv n \ (\text{mod } 5) &\Leftrightarrow \\
n^5 - n &= 5q &\Leftrightarrow  \\
5\ &|\ (n^5 - n).
\end{aligned}
\end{equation}
$$
On the other hand
$$
n^5 - n = n(n-1)(n^3+n^2+n+1). \ \ \ \ \ \ \ \ \ \ \ \ \text{(a)}
$$
As both $2$ and $5$ are divisors of $(n^5 - n)$ we can conclude that
$$
n^5 \equiv n\ (\text{mod } 10). \ \ \ \ \ \text{QED}
$$
I understand the given result as well as the theorems it build upon. I also can easily see that $5$ is a divisor of $(n^5 - n)$. As I keep the target in mind I also can figure out that the only missing part of this proof would be to figure out a way to show that $2$ is also a divisor of $(n^5 - n)$.
At first equation $(a)$  did not make any sense to me. After checking the case where $n$ is odd as well as the case where $n$ is even, I did find out that the equation results in an even number in both cases.
My question, sorry for the very long introduction, goes as follows:
Should I wanted to have proven this myself. What approach would have lead me to trying to factor $(n^5 - n)$ to the given equation $(a)$? In fact while it is easy fo to factor from right to left in that equation, I do not easily see how one would go from left to right? Probably I am missing some fundamental mathematical knowledge here. Can anyone please help me figure out how would exactly figure that out? Is it trial and error? Is it just knowing some specific concepts? What knowledge am I missing here?
 A: This is trivial:


*

*If $n$ is odd, is $n^5-n$ odd or even?

*If $n$ is even, is $n^5-n$ odd or even?
A: 1) Also by fermat  $n^2 \equiv n \pmod 2$. so $n^5\equiv n^4\equiv n^3\equiv n^2 \equiv n\pmod 2$ so $n^5-n\equiv 0 \pmod 2$.
2) In simpler explanation of 1)  $n$ is either equiv $1$ or $0\pmod 2$.  If $n\equiv 1\pmod 2$ then $n^5-n\equiv 1-1\equiv 0\pmod 2$ and if $n\equiv 0 \pmod 2$ then $n^5 -n\equiv 0 \pmod 2$.
3) But what the text is doing is factoring $n^5 -n = n(n^4 - 1)=n(n^2-1)(n^2+1) = n(n-1)(n+1)(n^2 + 1) = n(n-1)(n^3 + n^2 + n+1)$.
The $n^3 + n^2 + n+1$ will not be relevant. 
But $n$ and $n-1$ are.  One of them must be even.  And if one of them is even the entire product is even.
Bear in mind "$n\equiv 0 \pmod 2$" and "$n$ is even" are the exact same statements.
=====
Arithmetic on $\mod 2$ is presumed to be very easy.
Keeping in mind $n\equiv 0 \pmod 2 \iff n$ is even and $n\equiv 1\pmod 2 \iff n$ is odd;
We actually learned everything there is to know about $\mod 2$ in elementary school when we learned:
$even\times even = even$
$odd\times even = even$
$odd \times odd = odd$
$even + odd = odd$
$even + even = even$
$odd + odd = odd$.
That is EVERYTHING you need to know.
.....
$n^k;k > 0$ is either $even^k=even$ or $odd^k=odd$.  Either way:  $n^k \equiv n\pmod 2$.
A: There is already one answer, however you can use fermat's little theorem in the following way:

Fermat's little theorem states that if $a$ and $p$ are coprime, then $a^{p-1}\equiv 1(\text{mod} p)$ (and as fleablood pointed out $a^{p}\equiv a(\text{mod} p)$, whenever p is prime)

As a result, $n^5\equiv n\cdot (n^2)^2\equiv n^2\equiv n(\text{mod} 2)$, so $n^5-n\equiv 0(\text{mod} 2)$ and so your desired result follows
A: If $n$ is even, then $n = 2k$ with $k\in Z$. Substituting, I obtain: $32k^5-2k$; in other words $2k(16k^4-1)$. This is always divisible by $2$. 
If $n$ is odd, then $n=2k+1$ with $k\in Z$. Substituting, I obtain: $(2k+1)^5-2k-1$; in other words: $32k^5+16\cdot5k^4+10\cdot8k^3+10\cdot 4k^2+5\cdot 2k+1-2k-1=32k^5+80k^4+80k^3+40k^2+8k=2k(16k^4+40k^3+40k^2+20k+4)$  that is still divisible by 2.
A: To factor $n^5-n$, first factor out $n$:  $n^5-n=n(n^4-1)$.
Now use difference of squares:  $n^4-1=(n^2+1)(n^2-1)$.
And again:  $n^2-1=(n+1)(n-1)$.
Putting it all together, $n^5-n=n(n^2+1)(n+1)(n-1)$.  
If $n$ is even, then $n^5-n$ is even, since a product with an even factor is even.
If $n$ is odd, then $n\pm1$ is even, so $n^5-n$ is even.
A: *

*For the factorisation: it results from high-school well known formulæ:
$$n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1)=n(n-1)(n^3+n+n^2+1).$$

*For divisibility by $2$: let's use congruences modulo $2$.
Lil' Fermat says that, for every $n$, $n^2\equiv n\bmod 2$, so $n^4\equiv n^2\equiv$ and ultimately $\;^5=n\cdot n^4\equiv n\cdot n\equiv n$, so $$n^5-n\equiv n-n=0\mod 2.$$
A: $$2x+2x=2y;2x+1+2x+1=4x+2=2z;2x+2x+1=4x+1=2y+1$$
from theses you can prove multiplication rules like odd times odd is odd. and if that second number is the same as the first, that's exponentiation if repeated. A power has the same parity as it's base can then be proved. $n$ is our base in $n^5$. 
