Proof
(related to Proposition: A Necessary Condition for an Integer to be Prime)
- According to the explicit formula for the Euler function, we have $\phi(p)=p-1$ for any prime number $p.$
- Note that if $p$ is not a divisor of $a$ then both are co-prime.
- Therefore, $a^{p-1}(p)\equiv 1(p)$ follows immediately from Fermat's little theorem for a prime module.
- Multiplying both sides gives us the congruence with $a^p(p)\equiv a(p).$
- If $p\mid a,$ then trivially $a^p(p)\equiv 0(p)\equiv a(p).$
- Therefore, the congruence $a^p(p)\equiv a(p)$ holds for all prime numbers $p$ and all integers $a,$ (i.e. no matter if $p\mid a$ or $p\not\mid a$).
∎
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
