Đị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) $
Chứng minh
1) Ta có $ a-c=a-b+b-c $, mà $ a\equiv b(mod n), b\equiv c(mod n) $ nên $ a-b\vdots n, b-c\vdots n $, do đó $ a-c \vdots n $ hay $ a\equiv c(mod n) $.
2) $ a-b=(a\pm c)-(b\pm c) $, do đó $ a\equiv b(mod n) \Leftrightarrow a\pm c \equiv b\pm c(mod n) $
3) $ a+c-(b+d)=(a-b)+(c-d)\vdots n $, suy ra $ a+c\equiv b+d(mod n) $
4) Do $ a\equiv b(mod n) $ nên $ a-b\vdots n\Rightarrow ca-cb\vdots n$với mọi số nguyên c. Do đó $ ca\equiv cb(mod n) $.
5) Ta có $ (a^k-b^k)\vdots (a-b) $ với mọi số tự nhiên k. Do đó nếu $ a\equiv b (mod n) $ thì $ a^k\equiv b^k(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 $$.