Some Remarks of proofs of Fermat's little theorem
September 2022
In the last few years I've encountered and discussed proofs of Fermat's little Theorem several times: While preparing our book, talking with Sylvy in a Bourbaki meeting, trying to calm down my TAs when I gave it as an exercise in linear algebra for first year students, and recently while preparing my lectures for MATH/PHYS preparation week and seeing this post in mathoverflow. I would like to record here my two cents on the topic (and use this opportunity in order to check the latex possibilities of the our ISG Markdown web-platform).
The main Meta-Mathematical point that all the people mentioned above made, is that Fermat's little theorem is an "abelian" statement, so proving it via Lagrange's Theorem on general subgroups does not really make sense. Therefore, the "preferred" proof is via modular arithmetic, as we do in [3]. But this uses quite a lot of language, or even in some sense abelian group theory. Hence, maybe even just out of pedagogical interests, one may look for an "elementary" proof.
The main "mathematical" point I'd like to add, is that knowing that $p \choose r$ for $1<r<p$ is always divisible by $p$, makes the straight-forward proof by induction work (as done for $p=2$ in [2]). I will record shortly the details here.
Here is the theorem in a convient form for induction, stemming from the discussion in [2].
Fermat's little Theorem: Let $p$ be a prime number. For any $n\in \mathbb N$ we have that $n^p-n$ is divisible by $p$.
We want to do a proof by induction using the binomial expansion
$$(x+y)^{m}=\sum_{k=0}^{m}{m \choose k}x^{m-k}y^{k}.$$
Let's try the obvious induction on $n$ and see what we need. Assuming that $n^p-n$ is divisible by $p$ we examine $(n+1)^p-(n+1)$ and use the binomial expansion with $m=p$.
$$(n+1)^p-(n+1)=\left (n^p + \left (\sum_{k=1}^{p-1}{p \choose k}n^{p-k}1^{k}\right ) +1\right )-n-1=$$
$$=(n^p-n) + \sum_{k=1}^{p-1}{p \choose k}n^{p-k}1^{k}.$$
So... if we know that for $1<k<p$, the binomial coefficient ${p\choose k}$ is always divisible by $p$, we will be done! This is not too hard to show. Here is an argument (compare with [1]):
A proof that ${p\choose k}$ for $1<k<p$ is divisible by $p$ : We know that ${p \choose k}$ is an integer and that it equals a ratio of two products of integers $\frac{p!}{(p-k)!k!}$. The prime number $p$ appears in the numerator $p!$. But since $1<k<p$, the denominator $(p-k)!k!$ only contains terms which are smaller than $p$, and therefore the prime $p$ does not appear in their prime factorisation. So, no term in the denominator can cancel $p$ out. This means that $p$ must appear in the prime factorisation of ${p \choose k}$.
References mentioned above:
[1] Sylvy's Post
[3] Our book