Relating two forms of little Fermat: $a^p\equiv a$ vs. $a^{p-1}\equiv 1$ if $p\nmid a$

Question

I know that if $p$ prime and $p\nmid a$, then $a^{p-1}\equiv 1\pmod p$ and I know also that $a^{p}\equiv a \pmod p$ using the fact $a\equiv a \pmod p$ and multiplying the members.

What I couldn't understand is why in the Fermat little theorem we have $a^{p}\equiv a \pmod p$ for all integer $a$.

Answer 1

Following the comments of André Nicholas:

If $p\mid a$, then $a\equiv 0 \pmod p$, then multiplying $p$ times both sides we have $a^p\equiv 0 \pmod p$. Thus we have $a\equiv 0 \pmod p$ and $0\equiv a^p\pmod p$ by symmetry, then finally by transitivity:

$$a\equiv a^p \pmod p$$

Answer 2

Either $p$ divides $a$ or $p\nmid a$

As $p$ is prime $p\nmid a\implies (a,p)=1$

As $\displaystyle a^p-a=a(a^{p-1}-1)$

This will be divisible by $p$ if $p|a$

otherwise it will also be divisible by $p$ as $p|(a^{p-1}-1)$ by Fermat little theorem

Answer 3

If $p$ divides $a$ then both $a^p$ and $a$ are congruent to $0$, so $a^p\equiv a\pmod{p}$ holds trivially.

Remark: From $a^p\equiv a\pmod{p}$, we can conversely derive the more common form of Fermat's Theorem. For if $a^p\equiv a\pmod p$, then $p$ divides $a(a^{p-1}-1)$. So if $p$ does not divide $a$, then $p$ divides $a^{p-1}-1$.

Answer 4

It is instructive to view this from a slightly more general perspective. The equivalence of the two common forms of the Little Fermat theorem is special case $\, f(x) = x^{p-1}-1\,$ below.

Theorem $\ $ If $\,p\,$ is prime and $f(x)$ is polynomial with integer coefficients then $$\begin{align} &p\mid x f(x)\ \text{ for all integers } x\\[.2em] \iff\ &p\mid f(x) \ \ \ \:\! \text{ for all integers } x\ \text{coprime to } p \end{align}$$

Proof $\ (\Rightarrow)\ $ By hypothesis $\,p\mid xf(x),\,$ so $\,x\,$ coprime to $\,p\Rightarrow\,p\mid f(x)\,$ by Euclid's Lemma.

$(\Leftarrow)\ $ We split into two cases depending on whether or not $\,p\mid x$.

Case $(1)\ \ p\mid x.\ $ Then $\,p\mid xf(x).$

Case $(2)\ \ p\nmid x,\,$ so $\,x\,$ is coprime to $\,p,\,$ so by hypothesis $\,p\mid f(x)\,$ so $\,p\mid xf(x).\ $ QED

Remark $\, $ If you know modular arithmetic then it can be viewed more arithmetically as the following in the $\color{#0a0}{\rm domain}$ $R=\Bbb Z_p$ (true for a polynomials over any field or domain)

$$\begin{align} \forall x\!:&\ \ \ \ \ \ \ xf(x)= 0\\[.2em] \iff\ \forall x\ &\ [\:\!x\not= 0\Rightarrow f(x)= 0\:\!]\\[.6em] {\rm generally}\quad \forall x\!:&\ \ \ \ \ \ g(x)\:\!f(x)= 0\\[.2em] \iff \ \forall x\ &\ [\:\!g(x)= 0\ \ {\rm or}\ \ f(x)= 0\:\!]\ \ \text{by $\,R\,\ {\rm a}\ \color{#0a0}{\rm domain}$}\\[.2em] \iff\ \forall x\ &\ [\:\!g(x)\not= 0\,\Rightarrow\:\! f(x)= 0\:\!]\end{align}$$