Đồng dư và số học modulo

Đây chính là điều khiến đồng dư dùng được như số học: nghĩa là ta có thể cộng, trừ, nhân trực tiếp trên số dư thay vì các số gốc rất lớn, và luôn nhận lại số dư đúng — lý do máy tính có thể kiểm tra một số thẻ $16$ chữ số hay tính $7^{100} \bmod 13$ mà không bao giờ phải lưu một số có $100$ chữ số.

Phản xạ: $a-a=0$ và $m\mid 0$ với mọi $m$, nên $a\equiv a\pmod m$.

Đối xứng: nếu $a\equiv b\pmod m$ thì $a-b=mk$ với một số nguyên $k$ nào đó, suy ra $b-a=m(-k)$; vì $-k$ cũng là số nguyên nên $m\mid(b-a)$, tức $b\equiv a\pmod m$.

Bắc cầu: nếu $a\equiv b\pmod m$ và $b\equiv c\pmod m$, viết $a-b=mk_1$ và $b-c=mk_2$. Cộng hai đẳng thức: $a-c=(a-b)+(b-c)=m(k_1+k_2)$, nên $m\mid(a-c)$ và $a\equiv c\pmod m$.

Tương thích với phép cộng: từ $a-b=mk_1$ và $c-d=mk_2$, cộng hai phương trình: $(a+c)-(b+d) = m(k_1+k_2)$, là một bội của $m$, nên $a+c\equiv b+d\pmod m$.

Tương thích với phép nhân: viết $ac-bd = ac-bc+bc-bd = c(a-b)+b(c-d) = c\cdot mk_1 + b\cdot mk_2 = m(ck_1+bk_2)$. Đây lại là một bội của $m$, nên $ac\equiv bd\pmod m$. Kết hợp (i)-(iii) làm cho đồng dư trở thành quan hệ tương đương, và hai bước cuối cho thấy mọi phép toán vành trên $\mathbb{Z}$ đều chuyển xuống thành phép toán xác định tốt trên các lớp thặng dư $\mathbb{Z}/m\mathbb{Z}$.

"Chia" thông thường thực chất là nhân với nghịch đảo, và định lý này cho biết chính xác khi nào nghịch đảo đó tồn tại theo môđun $m$: đúng khi $c$ không có ước chung nào với $m$. Thiếu điều kiện này, phép giản ước thực sự thất bại (xem hàng cuối bảng trên), đó là lý do mọi kết quả sau này về lũy thừa theo môđun $m$ — định lý Fermat nhỏ, định lý Euler, định lý phần dư Trung Hoa — đều được xây trên chính sự kiện đại số duy nhất này.

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.