Proof using Mod How can you prove that: 
$$a^7\equiv a\:(\text{mod } 42)$$
I haven't been given any other information other than to use Fermat's theorem. 
 A: Hint:
Use Fermat's Theorem and the Chinese Remainder Theorem.
A: Note first $42 = 2\cdot 3\cdot 7$.
By Fermat's theorem, $a^2 \equiv a$ (mod 2).
Hence $a^3 \equiv a^2 \equiv a$ (mod $2$), etc.
Hence $a^7 \equiv a$ (mod $2$).
By Fermat's theorem, $a^3 \equiv a$ (mod 3).
Hence $a^7 = (a^3)^2a \equiv a^3 \equiv a$ (mod $3$).
By Fermat's theorem, $a^7 \equiv a$ (mod $7$).
Therefore $a^7 \equiv a$ (mod $42$).
A: Directly:
$$a^7=a\pmod{42}\Longleftrightarrow \,\,\exists \,k\in\Bbb Z\,\,\,s.t.\,\,\,a^7-a=42k\,\,,\,$$
But
$$(1)\;\;\;\;\text{If}\,a=0\pmod{42}\,\,,\,\text{ then the claim is obvious. Otherwise:}$$
$$a^7=a\pmod{42}\Longrightarrow a^6=1\pmod{42}\Longleftrightarrow \exists\,k\in\Bbb Z\,\,s.t.\,\,a^6-1=42k$$
But:
$$a^6-1=(a^3-1)(a^3+1)=(a-1)(a^2+a+1)(a+1)(a^2-a+1)$$
Now check all the cases and verify the above is always divisible by $\,2\,,\,3\,,\,and\,\,7\,$
A: There are two versions of Fermat's Theorem. 
Version $1$: If $a$ is not divisible by $p$, then $a^{p-1}\equiv 1\pmod{p}$.
Version $2$: For any $a$, $a^p\equiv a\pmod p$.
The more common version is Version $1$. From it, you can easily deduce Version $2$. For if $a$ is not divisible by $p$, then $a^{p-1}\equiv 1\pmod{p}$. Multiplying by $a$, we get that $a^p\equiv  a \pmod{p}$. On the other hand, if $a$ is divisible by $p$, we have that both $a^p$ and $a$ are congruent to $0$ modulo $p$, and therefore are congruent to each other.
We omit the proof that Version $2$ implies Version $1$. It is straightforward.
Using Version $2$, we find that for all $a$,
$$a^7 \equiv a\pmod{7}.\tag{$1$}$$
Now work modulo $2$. It is hardly necessary to use machinery. If $a$ is odd, then so is $a^7$, and if $a$ is even, then so is $a^7$.  We conclude that for all $a$, 
$$a^7 \equiv a\pmod{2}.\tag{$2$}$$
Now work modulo $3$. We can do a three-cases verification that $a^7\equiv a\pmod{3}$ for all $a$. Or else we can use Fermat's Theorem. If $a$ is divisible by $3$, then $a^7$ and $a$ are congruent to $0$ modulo $3$, so they are conruent to each other. If $a$ is not divisible by $3$, then $a^2\equiv 1\pmod{3}$, and therefore $a^6\equiv 1\pmod{3}$, and therefore $a^7\equiv a \pmod{3}$. we conclude that for all $a$
$$a^7 \equiv a\pmod{3}.\tag{$3$}$$
So $7$, $2$, and $3$ each divide $a^7-a$. Since they are pairwise relatively prime, it follows that their product $42$ divides $a^7-a$ for all $a$. This is what we wanted to prove. 
A: Hint $\rm\,\ x\!-\!1\mid x^n\!-\!1\:\Rightarrow\:a^{p-1}\!-\!1\mid a^{n(p-1)}\!-\!1\:\Rightarrow\:p\mid a^p\!-\!a\mid a^{1+\color{#C00}{n(p-1)}}\!-\!a\,\ $ by little Fermat.
So if $\rm\:p_i\:$ are distinct primes then $\rm\ p_i\!-\!1\mid \color{#C00}{m\!-\!1}\:\Rightarrow\: p_1\cdots p_k\mid a^m - a$
