Let $p$ be any prime greater than or equal to $5$. Prove that $a^p ≡ a \pmod{3p}$

elementary-number-theorymodular arithmetic

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.

Best Answer

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}$$.

Related Question