Let $p$ be any prime greater than or equal to $5$. Prove that $a^p ≡ a \pmod{3p}$ I am unsure how to prove the following statement, although I am fairly sure it has something to do with Fermat's Little Theorem, which states that $a^p \equiv a \pmod{p}$ for a prime, $p$. Any help is greatly appreciated.
 A: The second part can also be done like this:
Fermat's little theorem gives $a^3\equiv a \pmod{3}$, so
$$a^p = a^{p-3} a^3 \equiv a^{p-3} a \equiv a^{p-2} \pmod{3} \\ 
\Rightarrow a^p \equiv a^{p-2} \equiv a^{p-4} \equiv \cdots \equiv a \pmod{3}$$.
A: By Fermat's little theorem we have $a^{p} \equiv a \pmod {p}.$ We need to show that $a^p \equiv a \pmod {3}$. If $3$ does not divide $a$, we have $a^2 \equiv 1 \pmod {3}$ which implies that $a^{2j} \equiv 1 \pmod {3}$. Since the exponent is an odd prime, $p = 2j+1$ meaning that $a^p=a^{2j+1} \equiv a \pmod {3}$. Otherwise, we have $a= 3k$ for some $k \in \mathbb{Z}$ so that $a^{p}-a = (3k)^p - 3k = 3(3^{p-1}k^{p} - k)$. Since $(3,p) = 1$, by the chinese remainder theorem we have that $a^{p} \equiv a \pmod {3p}$.
A: Easy alternative (I hate math).
Known that $(3k+r)^n \equiv r^n\pmod{3}.$
$1^p \equiv 1\pmod{3} \implies (1^p - 1) \equiv 0\pmod{p}.$
Since $p$ is odd, $(p-1)$ is even.
$2^{(\text{any even #)}} \equiv 1 \pmod{3} \implies 2^{(p-1)} \equiv 1\pmod{3}.$
Therefore, $2^{p} \equiv 2^1\pmod{3}\implies (2^p - 2) \equiv 0\pmod{p}$
Therefore, since $a$ must be congruent (mod 3) to either $0,1,$ or $2$, $(a^p - a) \equiv 0\pmod{3}.$
