Luật giản ước và sự tồn tại nghịch đảo modulo

Vì $\gcd(c,m)=1$, đẳng thức Bézout (hệ quả của thuật toán Euclid) đảm bảo $\exists\, u,v \in \mathbb{Z}:\ cu+mv=1$: tồn tại các số nguyên $u,v$ với $cu+mv=1$.

Nhân cả hai vế của $ac\equiv bc\pmod m$ với $u$: $acu\equiv bcu\pmod m$. Thay $cu=1-mv$: vế trái trở thành $a(1-mv)=a-amv$, và vì $amv$ là bội của $m$ nên $a(1-mv)\equiv a\pmod m$; tương tự vế phải $b(1-mv)\equiv b\pmod m$. Do đó $a\equiv b\pmod m$, chứng minh luật giản ước.

Hơn nữa, không cần lấy $a=1,b=0,c=c$ — trực tiếp, cùng phép thay thế cho $cu = 1-mv \equiv 1 \pmod m$, nên chính $u$ là nghịch đảo nhân của $c$ theo môđun $m$: đây chính là đối tượng mà phát biểu định lý khẳng định sự tồn tại.

Giả thiết $\gcd(c,m)=1$ là thiết yếu: lấy $c=4,\ m=6$ (nên $\gcd(4,6)=2\neq1$). Khi đó $4\times 2=8\equiv 2\pmod 6$ và $4\times 5=20\equiv 2\pmod 6$, nên $4\times2\equiv 4\times5\pmod 6$, nhưng $2\not\equiv 5\pmod 6$ — luật giản ước thực sự thất bại một khi bỏ giả thiết nguyên tố cùng nhau.