Định lý Euler

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