TÀI LIỆU HỌC TẬP: ĐỒNG DƯ THỨC VÀ ỨNG DỤNG

Mục tiêu: Tài liệu này cung cấp kiến thức cơ bản và nâng cao về đồng dư thức, các tính chất quan trọng, và ứng dụng của nó trong giải toán, đặc biệt là các bài toán chia hết.

1. Định nghĩa và Ký hiệu

1.1 Định nghĩa

Cho $a, b$ là các số nguyên và $m$ là số nguyên dương. Ta nói $a$ đồng dư với $b$ theo modulo $m$, ký hiệu là $a \equiv b \pmod{m}$, nếu $a-b$ chia hết cho $m$.

Ví dụ:

• $17 \equiv 2 \pmod{5}$ vì $17 - 2 = 15$ chia hết cho 5.
• $-8 \equiv 7 \pmod{5}$ vì $-8 - 7 = -15$ chia hết cho 5.
• $23 \equiv 3 \pmod{10}$ vì $23 - 3 = 20$ chia hết cho 10.

1.2 Nhận xét

• $a \equiv b \pmod{m}$ khi và chỉ khi $a$ và $b$ có cùng số dư khi chia cho $m$.
• $a \equiv 0 \pmod{m}$ khi và chỉ khi $a$ chia hết cho $m$.
• Mọi số nguyên $a$ đều đồng dư với số dư $r$ của phép chia $a$ cho $m$, tức là $a \equiv r \pmod{m}$, trong đó $0 \leq r < m$.

2. Các Tính chất Cơ bản của Đồng dư thức

2.1 Tính chất phản xạ

$a \equiv a \pmod{m}$

2.2 Tính chất đối xứng

Nếu $a \equiv b \pmod{m}$ thì $b \equiv a \pmod{m}$

2.3 Tính chất bắc cầu

Nếu $a \equiv b \pmod{m}$ và $b \equiv c \pmod{m}$ thì $a \equiv c \pmod{m}$

2.4 Tính chất cộng

Nếu $a \equiv b \pmod{m}$ và $c \equiv d \pmod{m}$ thì $a+c \equiv b+d \pmod{m}$

2.5 Tính chất trừ

Nếu $a \equiv b \pmod{m}$ và $c \equiv d \pmod{m}$ thì $a-c \equiv b-d \pmod{m}$

2.6 Tính chất nhân

Nếu $a \equiv b \pmod{m}$ và $c \equiv d \pmod{m}$ thì $ac \equiv bd \pmod{m}$

Hệ quả:

• Nếu $a \equiv b \pmod{m}$ thì $a^n \equiv b^n \pmod{m}$ với mọi số nguyên dương $n$.
• Nếu $a \equiv b \pmod{m}$ thì $ka \equiv kb \pmod{m}$ với mọi số nguyên $k$.

2.7 Tính chất chia

Nếu $ac \equiv bc \pmod{m}$ và $\gcd(c, m) = d$ thì $a \equiv b \pmod{\frac{m}{d}}$

Trường hợp đặc biệt:

• Nếu $ac \equiv bc \pmod{m}$ và $\gcd(c, m) = 1$ thì $a \equiv b \pmod{m}$

3. Các Định lý Quan trọng

3.1 Định lý Fermat nhỏ

Nếu $p$ là số nguyên tố và $a$ là số nguyên không chia hết cho $p$ thì $a^{p-1} \equiv 1 \pmod{p}$.

3.2 Định lý Euler

Nếu $a$ và $m$ là các số nguyên tố cùng nhau (tức là $\gcd(a, m) = 1$) thì $a^{\phi(m)} \equiv 1 \pmod{m}$, trong đó $\phi(m)$ là hàm Euler.

Chú ý: Hàm Euler $\phi(m)$ là số các số nguyên dương nhỏ hơn hoặc bằng $m$ và nguyên tố cùng nhau với $m$.

Ví dụ: $\phi(10) = 4$ vì có 4 số nhỏ hơn 10 và nguyên tố cùng nhau với 10 là 1, 3, 7, 9.

3.3 Định lý Wilson

$p$ là số nguyên tố khi và chỉ khi $(p-1)! \equiv -1 \pmod{p}$.

4. Ứng dụng của Đồng dư thức trong Giải Toán Chia Hết

4.1 Chứng minh chia hết

Ví dụ 1: Chứng minh rằng $2^{100} - 1$ chia hết cho 3.

• Ta có $2 \equiv -1 \pmod{3}$.
• Suy ra $2^{100} \equiv (-1)^{100} \equiv 1 \pmod{3}$.
• Vậy $2^{100} - 1 \equiv 1 - 1 \equiv 0 \pmod{3}$, tức là $2^{100} - 1$ chia hết cho 3.

Ví dụ 2: Chứng minh rằng $3^{2n+1} + 2^{n+2}$ chia hết cho 7 với mọi số nguyên dương $n$.

• Ta có $3^2 \equiv 2 \pmod{7}$ và $2^3 \equiv 1 \pmod{7}$.
• $3^{2n+1} + 2^{n+2} = 3 \cdot (3^2)^n + 4 \cdot 2^n \equiv 3 \cdot 2^n + 4 \cdot 2^n \equiv 7 \cdot 2^n \equiv 0 \pmod{7}$

4.2 Tìm số dư

Ví dụ 1: Tìm số dư khi chia $7^{2023}$ cho 10.

• Ta có $7^1 \equiv 7 \pmod{10}$
• $7^2 \equiv 49 \equiv 9 \pmod{10}$
• $7^3 \equiv 7 \cdot 9 \equiv 63 \equiv 3 \pmod{10}$
• $7^4 \equiv 7 \cdot 3 \equiv 21 \equiv 1 \pmod{10}$
• Vậy $7^{2023} = 7^{4 \cdot 505 + 3} = (7^4)^{505} \cdot 7^3 \equiv 1^{505} \cdot 3 \equiv 3 \pmod{10}$.
• Số dư là 3.

Ví dụ 2: Tìm số dư khi chia $2^{1000}$ cho 13.

• Theo định lý Fermat nhỏ, $2^{12} \equiv 1 \pmod{13}$.
• $2^{1000} = 2^{12 \cdot 83 + 4} = (2^{12})^{83} \cdot 2^4 \equiv 1^{83} \cdot 16 \equiv 16 \equiv 3 \pmod{13}$.
• Số dư là 3.

4.3 Giải phương trình đồng dư

Bài toán: Tìm tất cả các số nguyên $x$ thỏa mãn $ax \equiv b \pmod{m}$.

Phương pháp:

1. Tìm $d = \gcd(a, m)$. Nếu $b$ không chia hết cho $d$ thì phương trình vô nghiệm.
2. Nếu $b$ chia hết cho $d$, chia cả ba số $a$, $b$, $m$ cho $d$, ta được phương trình tương đương: $\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}}$.
3. Tìm nghịch đảo modular $a'$ của $\frac{a}{d}$ theo modulo $\frac{m}{d}$, tức là tìm $a'$ sao cho $\frac{a}{d}a' \equiv 1 \pmod{\frac{m}{d}}$.
4. Nhân cả hai vế của phương trình với $a'$, ta được $x \equiv a'\frac{b}{d} \pmod{\frac{m}{d}}$.
5. Nghiệm tổng quát là $x = a'\frac{b}{d} + k\frac{m}{d}$, với $k$ là số nguyên.

Ví dụ: Giải phương trình $3x \equiv 5 \pmod{7}$.

1. $\gcd(3, 7) = 1$ và 5 chia hết cho 1.
2. Nghịch đảo modular của 3 theo modulo 7 là 5 vì $3 \cdot 5 = 15 \equiv 1 \pmod{7}$.
3. Nhân cả hai vế với 5, ta được $15x \equiv 25 \pmod{7}$, suy ra $x \equiv 4 \pmod{7}$.
4. Nghiệm tổng quát là $x = 4 + 7k$, với $k$ là số nguyên.

5. Bài tập tự luyện

1. Chứng minh rằng $3^{3n+1} + 2^{n+2}$ chia hết cho 5 với mọi số nguyên dương $n$.
2. Tìm số dư khi chia $2023^{2024}$ cho 7.
3. Chứng minh rằng $n^3 + 5n$ chia hết cho 6 với mọi số nguyên $n$.
4. Giải phương trình đồng dư $5x \equiv 3 \pmod{8}$.
5. Chứng minh rằng nếu $p$ là số nguyên tố lớn hơn 3 thì $p^2 \equiv 1 \pmod{24}$.

6. Tài liệu tham khảo

• Số học - Tác giả: Nguyễn Hữu Điển
• Các bài toán số học chọn lọc - Tác giả: Phan Huy Khải
• Tuyển tập 30 năm các bài toán Olympic Toán THPT

Chúc các bạn học tốt!