Định lý Fermat nhỏ, định lý Euler

Các thặng dư khác không theo môđun một số nguyên tố $p$ lập thành một hệ đóng dưới phép nhân: nhân mỗi thặng dư đó với một $a$ cố định chỉ xáo trộn chúng trong chính tập đó. Lặp lại việc xáo trộn này $p-1$ lần vì thế phải đưa mọi phần tử về đúng vị trí của nó, đó chính xác là phát biểu $a^{p-1}\equiv1\pmod p$.

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.)

Đây chính là lập luận của Fermat với môđun tổng quát $n$: thay vì mọi thặng dư khác không (chỉ lập thành hệ nhân đóng khi $n$ nguyên tố), ta giới hạn vào các thặng dư thực sự nguyên tố cùng nhau với $n$ — những thặng dư có nghịch đảo — và cùng lập luận xáo trộn áp dụng cho tập đóng nhỏ hơn này có kích thước $\varphi(n)$.

Gọi $R=\{r_1,\dots,r_{\varphi(n)}\}$ là một hệ thặng dư thu gọn theo môđun $n$: đại diện của mọi lớp thặng dư nguyên tố cùng nhau với $n$.

Phép nhân với $a$ hoán vị $R$: với mỗi $r_i$, $\gcd(ar_i,n)=1$ vì $\gcd(a,n)=1$ và $\gcd(r_i,n)=1$ (một tích nguyên tố cùng nhau với $n$ khi và chỉ khi cả hai thừa số đều vậy), nên $ar_i \bmod n$ lại là thành viên của các lớp thặng dư nguyên tố cùng nhau; và ánh xạ $r_i\mapsto ar_i \bmod n$ đơn ánh theo luật giản ước, vì $\gcd(a,n)=1$.

Một ánh xạ đơn ánh từ tập hữu hạn $R$ vào chính nó (theo thặng dư) là song ánh, nên $\{ar_1,\dots,ar_{\varphi(n)}\} \pmod n$ chỉ là $\{r_1,\dots,r_{\varphi(n)}\}$ được sắp lại.

Nhân tất cả $\varphi(n)$ phần tử của mỗi tập: $a^{\varphi(n)}\, (r_1 r_2\cdots r_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod n$. Vì mỗi $r_i$ nguyên tố cùng nhau với $n$, nên tích $R=\prod r_i$ của chúng cũng vậy, tức $\gcd(R,n)=1$.

Giản ước $R$ ở cả hai vế (hợp lệ vì $\gcd(R,n)=1$) được $a^{\varphi(n)}\equiv1\pmod n$. $\blacksquare$

Đây lại là định lý Lagrange dưới một hình thức khác: các thặng dư nguyên tố cùng nhau với $n$ lập thành một nhóm cấp $\varphi(n)$ dưới phép nhân (nhóm đơn vị $(\mathbb{Z}/n\mathbb{Z})^{*}$), và cấp của mọi phần tử chia hết $\varphi(n)$.