Fermat’s little theorem

If p is prime, and p \nmid a, (i.e. \gcd(a,p)=1) then

(1)   \begin{equation*}  \boxed{a^{p-1}\equiv 1\pmod p} \end{equation*}

Or equivalently, if p is prime, then

(2)   \begin{equation*}  \boxed{a^{p}\equiv a\pmod p} \end{equation*}

Stated by Fermat 1640. Proved by Euler 1736, and by Leibniz (unpublished) about 50 years before that.


Proof
\gcd(a,p)=1 means that a has an inverse \pmod p, i.e. there’s a number n such that na\equiv 1 \pmod p.
The numbers 1,2,\dots,p-1 also have inverses \pmod p, because p is prime.
Consider the remainders of a,2a,\dots,(p-1)a on division by p:

    \[a \pmod p, \quad 2a \pmod p, \quad \dots, \quad (p-1)a \pmod p.\]

These are the numbers 1,2,\dots p-1 again in a different order, as they are nonzero and unequal \pmod p, since ja \equiv ka \pmod p would imply j \equiv k \mod p. It follows that:

    \begin{gather*} a\times 2a \times \cdots \times (p-1)a\equiv 1\times 2\times \cdots \times (p-1) \pmod p, \intertext{i.e.} a^{p-1}\times a \times \cdots \times (p-1)\equiv 1\times 2\times \cdots \times (p-1) \pmod p, \intertext{and therefore} a^{p-1}\equiv 1\pmod p \end{gather*}


Proof by induction (for a>0)
1. When a=1, obviously 1^p\equiv 1\pmod p.
2. Assuming a^{p}\equiv a\pmod p is true for every prime p, prove (a+1)^{p}\equiv a+1\pmod p.
From the binomial theorem,

    \[(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots+\binom{p}{p-1}a+1.\]

Since p divides each of the integers \binom{p}{1},\binom{p}{2},\dots,\binom{p}{p-1}

    \[ (a+1)^p\equiv a^p+1 \pmod p \]

We have assumed that a^{p}\equiv a\pmod p, so

    \[(a+1)^{p}\equiv a+1\pmod p\]

QED

Leave a Reply

Your email address will not be published.