1. Khái niệm

Với $m$ là một số nguyên khác $0$. Nếu $a-b$ là bội của $m$, lúc đó ta nói $a$  đồng dư với $b\mod m$ và ta viết $a\equiv b\pmod m$. Nếu $a$ không đồng dư với $b$ mod $m$, lúc đó ta viết $a\not\equiv b\pmod m$.

Ví dụ.  $31\equiv -9\pmod {10}$.

Nếu $a,\,b$ đều là các số nguyên lúc đó ta luôn có $a\equiv b\pmod 1$.

Khái niệm của đồng dư xảy ra thường xuyên và và trong ngay cả cuộc sống hằng ngày của chúng ta, một ví dụ đó là để xác định ngày trong tuần chúng ta sẽ xét đồng dư $\mod 7$. Trong lịch ở đất nước chúng tôi ta đếm số năm bằng việc xét đồng dư $\mod 60$.

2. Các tính chất và quy tắc cơ bản

Định lý 2.1.  Ta có một số tính chất và quy tắc cơ bản sau.

1. $a\equiv a\pmod m$ (phản xạ)
2. Nếu $a\equiv b,\,b\equiv c\pmod m$, lúc đó $a\equiv c\pmod m$(bắc cầu)
3. Nếu $a\equiv b$, lúc đó $b\equiv a$(đối xứng)

Những tính chất này nói lên rằng sự tồn tại đồng dư là một quan hệ tương đương. Tập của những số nguyên dương có thể phân chia vào hai lớp tương đương vì thế những số nguyên ở mỗi lớp đồng dư với nhau. Còn hai số nguyên ở hai lớp khác nhau thì không đồng dư. Chúng ta gọi những lớp tương đương này là lớp thặng dư. Rõ ràng rằng, với modulus $m$ ta có chính xác $m$ lớp thặng dư. Lớp đó có những phần tử có số dư $r=0,\,1,\,2,\,3,\,\ldots m-1$ khi chia $m$.

Ta lấy một phần tử ở mỗi lớp, lúc đó tập của những số có dạng như thế gọi là một hệ thặng dư đầy đủ

Định lý 2.2.  Nếu $a\equiv b\pmod m,\,a_1\equiv b_1\pmod m$ lúc đó ta có $a+a_1\equiv b+b_1,\,a-a_1\equiv b-b_1,\,aa_1\equiv bb_1 \pmod m$.

Định lý 2.2 có lời giải thích sau đây; Với $A,\,B$ là hai lớp thặng dư bất kì có được từ việc lấy các đại diện $a,\,b$ bất kì. Ta kí hiệu lớp thặng dư có chứa $a+b$(hoặc $a-b,\,ab$) là $C$. Khi đó $C$ phụ thuộc vào $A,\,B$ nhưng không phụ thuộc vào $a,\,b$. Nói cách khác tổng của hai số nguyên bất kì từ $A,\,B$ phải thuộc về $C$. Từ đó ta có thể định nghĩa $C$ là tổng của hai lớp $A$ và $B$ và ta kí hiệu $C=A+B$. Tương tự ta có thể định nghĩa $A-B$ và $AB$. Ta thấy từ Định lý 2.2 rằng với đối với lớp thặng dư $\mod m$ ta thấy sự đóng giữa các phép toán cộng, trừ, nhân. Ta chú ý rằng không phải lúc nào ta cũng có thể giản ước các ước số chung giữa các vế đồng dư một ví dụ để minh chứng cho việc này đó là

Ví dụ. $3.2\equiv 1.2 \pmod 4,\,2\equiv 2\pmod 4$ nhưng $3\not\equiv 1\pmod 4 $

Từ đó ta có ngay một định lý để làm rõ vấn đề đó

Định lý 2.3  Nếu $ac\equiv bd\pmod m,\,c\equiv d\pmod m$ và $\gcd ( c,\,m)=1$, lúc đó $$a\equiv b\pmod m.$$

Chứng minh. Từ $(a-b)c+b(c-d)=ac-bd\equiv 0\pmod m$, ta có $$m\mid (a-b)c.$$ Nhưng $\gcd(c,\,m)=1$, vì thế $m\mid (a-b)$.
Ta kí hiệu lớp thặng dư của tất cả các ước của $m$ là $O$. Khi đó $A+O=A$ và $A.O=O$. Ta lại kí hiệu lớp thặng dư của những số nguyên chia $m$ dư $1$ là $I$, lúc đó $A.I=A$. Từ ví dụ của chúng ta và Định lý 2.3 ta thấy từ $A.B=A.C$ ta chưa thể kế luận rằng $B=C$; nhưng nếu các phần tử của $A$ đều nguyên tố cùng nhau với $m$ (Chú ý: nếu $A$ có một phần tử nguyên tố cùng nhau với $m$ thì khi đó toàn bộ phần tử của $A$ phải nguyên tố cùng nhau với $m$,) khi đó ta có $B=C$.

Nếu ta lấy $m$ là số nguyên tố thì lúc đó ngoài lớp $O$ tất cả các lớp còn lại đều nguyên tố cùng nhau với $m$. Từ đó, với một modulus nguyên tố, ta thấy tính đóng của tất cả các phép toán cộng trừ nhân chia, ngoại trừ việc ta không thể chia cho lớp $O$.

3. Hệ thặng dư thu gọn

Như ta đã nói từ trước, nếu một phần tử của lớp thặng dư $A$ nguyên tố cùng nhau với $m$ thì lúc đó tấ cả các phần tử của lớp thặng dư $A$ cũng nguyên tố cùng nhau với $m$, và ta gọi $A$ là bậc nguyên tố cùng nhau với $m$. Và ta gọi $A$ là một lớp nguyên tố cùng nhau với $m$. Nếu $A$ và $m$ nguyên tố cùng nhau, khi đó nhờ Đinh lý 2.3, định nghĩa $B\mid A$ ta có thể. Trong trường hợp đặc biệ, ta viế $A^{-1}$ thay cho $I\mid A$. Ví dụ……

Định nghĩa. Ta kí hiệu số lớp thặng dư $\pmod m$ nguyên tố cùng nhau với $m$ là $\varphi (m)$. Hàm $\varphi(m) $ được gọi là phi hàm Euler. Nếu ta chọn một phần tử của mỗi lớp thặng dư nguyên tố cùng nhau $\mod m$: \[a_1,\,a_2,\,\ldots,a_{\varphi (m)},\] khi đó ta gọi tập của những số nguyên này là hệ thặng dư thu gọn.

Ví dụ. $\varphi (1)=1,\,\quad \varphi (2)=1,\,\quad \varphi (3)=2,\,\quad \varphi (4)=2$.

Ta cũng định nghĩa số các số nguyên dương không vượt quá $m$ và nguyên tố cùng nhau với $m$ là $\varphi (m)$. Nếu $m=p$ là một số nguyên tố, lúc đó $\varphi (p)=p-1$.

Định lý. Với $a_1,\,a_2,\,\ldots,a_{\varphi(m)}$ là một hệ thặng dư thu gọn, và giả sử rằng $\gcd(k,\,m)=1$. Khi đó $ka_1,\,ka_2,\,\ldots,ka_{\varphi(m)}$ cũng là một hệ thặng dư thu gọn.

Chứng minh. Rõ ràng ta có $\gcd\left  (ka_i,\,m\right)=1$, vì thế mỗi $ka_i$ là đại diện cho mộ lớp thặng dư nguyên tố cùng nhau với $m$. Nếu $ka_i\equiv ka_j\pmod m$, lúc đó từ $\gcd(k,\,m)=1$, ta có $a_i\equiv a_j \pmod m$. Từ đó mỗi phần tử $ka_i$ đại diện cho những lớp thặng dư khác nhau và đây là điều cần chứng minh.

Định lý. (Euler). Nếu $\gcd(k,\,m)=1$, lúc đó $k^{\varphi(m)}\equiv 1\pmod m$.

Chứng minh. Từ Định lý 3.1 ta có \[\prod\limits_{v = 1}^{\varphi (m)} {(k{a_v})} \equiv \prod\limits_{v = 1}^{\varphi (m)} {({a_v})} \quad \left( {\bmod m} \right).\] Từ $\gcd\left (m,\,a_i\right)=1,$ nó dẫn đến $k^{\varphi(m)}\equiv 1\pmod m$.

Chọn $m=p$ ta có Định lý Fermat (Định lý 1.12.4).

Định lý. Với $p$ là một số nguyên tố. Lúc đó với số nguyên $a$ bất kì ta luôn có \[a^p\equiv a \pmod m.\]