Định nghĩa. Cho hai số nguyên $a,b$ và số tự nhiên $n$. Nếu $a,b$ chia cho $n$ có cùng số dư, ta nói rằng $a$ và $b$ đồng dư khi chia cho $n$ và kí hiệu $ a \equiv b (mod n)$ (đọc là $a$ đồng dư $b$ theo modul $n$).

Nhận xét. $ a \equiv b (mod n) \Leftrightarrow (a-b) \vdots n $

Ví dụ 1. $ 28 \equiv 3(mod5) $

Định lý. Cho $a, b, c$ là các số nguyên, $n$ là số nguyên dương.
1) Nếu $ a\equiv b(mod n), b \equiv c(mod n) $ thì $ a \equiv c(mod n) $
2) Nếu $ a\ \equiv b(mod n)$ thì $ a\pm c \equiv b\pm c(mod n) $ với mọi số nguyên c.
3) Nếu $ a\equiv b(mod n), c \equiv d(mod n) $ thì $a+c \equiv b+d(mod n)$
4) Nếu $ a\equiv b(mod n)$ thì $ c.a\equiv c.b(mod n) $ với mọi số nguyên c.
5) $ a\equiv b(mod n) $ thì $ a^k\equiv b^k(mod n) $ với mọi số nguyên dương k. Đặc biệt nếu $ a\equiv 1(mod n) $ thì $ a^k \equiv 1(mod n) $

Ví dụ 2. Chứng minh rằng với mọi số tự nhiên n thì $ 6^{2n}+2^{3n+2}+4 $ chia hết 7.

Ta có $ 6\equiv-1(mod 7) $, suy ra $ 6^{2n}\equiv (-1)^{2n}(mod n)\equiv 1(mod n) $
Và $ 2^{3n+1}=2.8^n\equiv 1(\mod 7) $ nên $ 2^{3n+1}\equiv 2(mod 7) $
Do đó $ 6^{2n}+2^{3n+1}+4\equiv2+1+4\equiv0(mod 7) $ hay $ 6^{2n}+2^{3n+1}+4\vdots7 $.

Định lý 27. Cho a, b là các số nguyên, $ m_1, m_2 $ là các số tự nhiên thỏa $ a\equiv b(mod m_1), a\equiv b\ (mod m_2) $ và $ (m_1, m_2)=1 $ thì $ a\equiv b(mod m_1\cdot m_2) $.

Chứng minh. Ta có $ m_1|(a-b) $ và ($ m_1, m_2 $)=1 thì $ m_1.m_2|(a-b) $. Từ đó suy ra điều cần chứng minh.\

Bài tập rèn luyện

Bài 1. Cho $n$ là số tự nhiên. Tìm chữ số tận cùng của các số $ 2^n, 3^n, 4^n $.

Bài 2. Chứng minh rằng $ 1941^{1963}+ 1963^{1941}-1 $ chia hết cho 7.

Bài 3. Chứng minh $ 3^{n+2}+4^{2n+1} $ chia hết cho 13.

Bài 4. Tìm phần dư của $ 1! + 2!+…+10! $ khi chia hết cho 15.

trong đó $ n!= 1.2…(n-1)n. $

Bài 5. Tìm số nguyên dương nhỏ nhất m biết $ m \equiv 2\ (mod\ 6),\ m \equiv 2\ (mod\ 8) $

Bài 6. Chứng minh $ 2^{2^n} +5 $ là hợp số.

Bài 7. Cho $ a^2+b^2 \equiv 0\ (mod\ 3) $, chứng minh $ a \equiv 0\ (mod\ 3),\ b \equiv 0\ (mod\ 3) $.

Bài 8. Tìm hai chữ số tận cùng của số $ 9^{9^9} $.

Bài 9. Một lớp học khi sắp thành 2 hàng, 3 hàng, 5 hàng đều dư ra 1 em. Hỏi lớp học đó có bao nhiêu học sinh biết rằng số học sinh không nhiều hơn 50.

Bài 10. Chứng minh rằng nếu $ a_i \equiv b_i (mod\ m) $ với i = 1, 2, …,n thì

a) $$  \qquad \sum_{i=1}^{n} a_{i}\equiv\sum_{i=1}^{n} b_{i} \quad \text{(mod m)}$$

b) $$ \qquad \prod_{i=1}^{n} a_{i}\equiv \prod_{i=1}^{n} b_{i} \quad \text{(mod m)}$$

Trong đó $$ \qquad \sum_{i=1}^{n} {x_i} = x_1+x_2+…+x_n,\qquad \prod_{i=1}^{n} x_{i}=x_1, x_2…x_n $$.