Định lý Fermat nhỏ

Xét tập $S=\{1,2,\dots,p-1\}$ các thặng dư khác không theo môđun $p$, và ánh xạ $x \mapsto ax \bmod p$ gửi mỗi phần tử của $S$ tới một thặng dư.

Ánh xạ này đơn ánh trên $S$: nếu $ax\equiv ay\pmod p$ với $x,y\in S$, thì vì $\gcd(a,p)=1$, luật giản ước (đã chứng minh ở chủ đề trước) cho $x\equiv y\pmod p$, suy ra $x=y$ vì cả hai đều nằm trong $\{1,\dots,p-1\}$. Cũng không có $ax$ nào $\equiv 0\pmod p$ với $x\in S$, vì $p$ nguyên tố và không chia hết $a$ lẫn $x$. Vậy ánh xạ thực sự rơi lại vào trong $S$.

Một ánh xạ đơn ánh từ tập hữu hạn $S$ vào chính nó tự động là song ánh. Do đó $\{a\cdot1,a\cdot2,\dots,a\cdot(p-1)\} \pmod p$ chỉ đơn giản là $\{1,2,\dots,p-1\}$ được viết theo thứ tự khác.

Nhân tất cả $p-1$ phần tử của cả hai tập lại với nhau. Một bên ta được $(a\cdot1)(a\cdot2)\cdots(a\cdot(p-1)) = a^{p-1}\,(p-1)!$; bên kia, vì là cùng các số được sắp lại, ta được đúng $(p-1)!$. Vậy $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$.

Vì $p$ nguyên tố, không số nào trong $1,2,\dots,p-1$ chia hết cho $p$, nên $\gcd((p-1)!,p)=1$. Áp dụng luật giản ước một lần nữa để bỏ nhân tử chung $(p-1)!$ ở cả hai vế cho $a^{p-1}\equiv1\pmod p$. $\blacksquare$

(Phát biểu lại theo ngôn ngữ nhóm: các thặng dư khác không lập thành một nhóm cấp $p-1$ dưới phép nhân vì $p$ nguyên tố, và định lý Lagrange nói cấp của mọi phần tử — ở đây, số $k$ nhỏ nhất với $a^k\equiv1$ — phải chia hết cấp nhóm $p-1$; do đó $a^{p-1}\equiv1\pmod p$ tự động đúng.)