Month: May 2020

Fermat’s Little Theorem

One of the first results in any introduction to number theory is Fermat’s Little Theorem, so called in contrast to the Last Theorem, or indeed to any of Fermat’s other results.

Theorem 1 (Fermat’s Little Theorem). Let {p} be a prime number and let {a} be any integer. Then {a^{p}\equiv a\pmod{p}.}

In this post — aimed at students taking an introductory course in number theory — I want to explain the two proofs that I find to be the simplest. Neither is deep, but the second requires a tiny bit of group theory, whereas the first does not.

1. First proof: by binomial coefficients

We shall take as given that the binomial coefficients \binom{n}{r}:=\frac{n!}{r!(n-r)!}, for r\in\{0,\ldots,n\} are natural numbers. We also take as given the Binomial Theorem:

\displaystyle {(X+Y)^{n}=\sum_{i=0}^{n}\binom{n}{i}X^{i}Y^{n-i}.}

Fix a prime number {p}.

Lemma 2. For {r\in\{1,\ldots,p-1\}}, the binomial coefficient {\binom{p}{r}} is divisible by {p}.

Proof: Since {\binom{p}{r}} is an integer, {r!} divides {\frac{p!}{(p-r)!}=p(p-1)\cdot\ldots\cdot(p-r+1)}. Since {p} is prime, and {r<p}, it follows that {p} and {r!} are coprime. By Euclid's Lemma, {r!\mid(p-1)\cdot\ldots\cdot(p-r+1)}. Therefore {\frac{(p-1)!}{r!(p-r)!}} is an integer. \Box

Lemma 3. For integers {a,b} we have {(a+b)^{p}\equiv a^{p}+b^{p}\pmod{p}}.

Proof: Apply the Binomial Theorem and Lemma 1. \Box

It’s now a simple matter to give the first proof of Fermat’s Little Theorem.

Proof: Let {p} be a prime number, and let {S:=\{a\in\mathbb{Z}\;|\;a^{p}\equiv a\pmod{p}\}} be the set of integers satisfying the conclusion of the theorem. If {p} is odd, then {(-1)^{p}=-1}. Otherwise, if {p=2} then {(-1)^{2}=1\equiv-1\pmod{2}}. Thus {-1\in S}. Lemma 3 shows that {S} is closed under addition. Therefore {S=\mathbb{Z}}. \Box

2. Second proof: by Lagrange’s Theorem

The second strategy is reasonably simple. I think of it as the proof ‘by Lagrange’s Theorem’, but that is perhaps unfair since its use of Bézout’s Lemma is just as key.

Let {a,b\in\mathbb{Z}}. Then there exist {x,y\in\mathbb{Z}} such that {ax+by=\mathrm{gcd}(a,b).} .

The proof goes by showing that the set

\displaystyle {\{xa+yb\;|\;x,y\in\mathbb{Z}\}},

of {\mathbb{Z}}-linear combinations of {a,b}, is also the set of integer multiples of the greatest common divisor {\mathrm{gcd}(a,b)}.

Let {G} be a finite group, and let {H\leq G} be a subgroup. Then {|G|=|H|\cdot(G:H)}.

The proof of Lagrange’s Theorem is a straightforward counting proof. One shows that each coset of {H} has the same order, and that the cosets partition {G}.

Okay! Using these two ingredients, we get the second proof of Fermat’s Little Theorem.

Proof: Let {p} be a prime number. It is a consequence of Bézout’s Lemma that {\{1,\ldots,p-1\}} forms a group under multiplication modulo {p}. Moreover it is a group of order {p-1}. Thus, for each {b\in\{1,\ldots,p-1\}}, we have {b^{p}\equiv b\pmod{p}}.

Now let {c\in\mathbb{Z}}. If {c} is divisible by {p}, then certainly {c^{p}\equiv c\pmod{p}}. Otherwise, there exists {a\in\{1,\ldots,p-1\}} and {k\in\mathbb{Z}} such that {c=a+pk}. Then {a^{p}\equiv c^{p}\equiv c\equiv a\pmod{p}}, as required. \Box

To be perfectly honest, I find this second proof less satisfactory than the first. Relying on Bézout seems reasonable enough (we are interested in integer arithmetic after all), but relying on Lagrange is a bit silly. Lagrange’s Theorem is a statement about all finite groups, which is just far too strong for what we need.

However you get there, Fermat’s Little Theorem is an important result of elementary number theory.

Advertisement