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?
Best Answer
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?