Prove that $\forall n\in\Bbb N:3\mid n^7-n$ I started learning number theory and need help to understand a specific part in the solution of the following exercise. Here it is:

Show that $\forall n\in\Bbb N:3\mid n^7-n$.

Since $3$ is prime,
$$n^3\equiv n\bmod3\tag{*}$$
Therefore
$$n^7 = (n^3)^2 \cdot n \equiv n^2 \cdot n \equiv n^3 \equiv n \pmod{3} \implies n^7 \equiv n \pmod{3} \implies 3 \mid  n^7 - n.$$
The only part which I don't understand is the first assertion. I tried to use Fermat's theorem to prove it but since we require $(n, 3) = 1$ to use the latter theorem and $n \in \mathbb{N}$ it may not apply. I have tried a few numbers to convince me that the congruence $(*)$ is true but I would like to know how to prove it. 
 A: It is basically Fermat's Little Theorem, just written in a slightly different form. 
It seems you know that for a prime $p$ one has if $\gcd(a,p)=1$, then 
$a^{p-1}\equiv 1 \pmod{p}$. 
Multiplying this by $a$ you get  $a^{p}\equiv a \pmod{p}$ for $\gcd(a,p)=1$.
However if $\gcd(a,p)\neq 1$, then $p \mid a$ so that 
$a\equiv 0\pmod{p}$ and $a^{p}\equiv a \pmod{p}$ is thus also true.
Thus, one has $a^{p}\equiv a \pmod{p}$ for all $a$. 
A: We don't need $(n,3)=1$ for this statement of Fermats theorem because if $(n,3)=3$ then $n$ is divisible by $3$ and so is $n^3$ which implies $n^3\equiv n\equiv 0\pmod{3}$ so its trivially true, you can extend this to any prime i.e if $(n,p)=p$ then $n^p\equiv n\equiv 0\pmod{p}$.
A: use that $$n^7-n=n \left( n-1 \right)  \left( n+1 \right)  \left( {n}^{2}+n+1 \right) 
 \left( {n}^{2}-n+1 \right) 
$$
and we have $$3\mid(n-1)n(n+1)$$
A: One version of Fermat says that 

For any prime $p$ and any $n\in\mathbf N$, $$n^p\equiv n\mod p.$$

Indeed, if $n\wedge p=1$, then $n^{p-1}\equiv 1$, whence $n^p\equiv n\mod p$.
Otherwise, as $p$ is prime, $p\mid n$, i.e. $n\equiv 0\mod p$, so $n^p\equiv 0^p=0\mod p$.
A: Alternatively:
$$n \equiv 0,1,2 \pmod 3 \Rightarrow$$
$$n^7 \equiv 0^7,1^7,2^7 \equiv 0,1,2 \pmod 3$$
Hence:
$$n^7-n \equiv 0 \pmod 3.$$
