Định lý nhỏ Fermat để tìm số dư

ĐỊNH LÝ NHỎ FERMAT VÀ ỨNG DỤNG TÍNH SỐ DƯ

I. ĐỊNH LÝ NHỎ FERMAT

Định lý: Cho $p$ là một số nguyên tố và $a$ là một số nguyên không chia hết cho $p$. Khi đó, ta có:

$a^{p-1} \equiv 1 \pmod{p}$

Chứng minh (sử dụng quy nạp):

1. Trường hợp cơ sở: Với $a = 1$, ta có $1^{p-1} = 1 \equiv 1 \pmod{p}$.

2. Giả thiết quy nạp: Giả sử định lý đúng với $a = k$, tức là $k^{p-1} \equiv 1 \pmod{p}$.

3. Bước quy nạp: Ta cần chứng minh định lý đúng với $a = k + 1$. Xét khai triển nhị thức Newton:

$(k+1)^p = \sum_{i=0}^{p} \binom{p}{i} k^i = \binom{p}{0}k^0 + \binom{p}{1}k^1 + \binom{p}{2}k^2 + \dots + \binom{p}{p-1}k^{p-1} + \binom{p}{p}k^p$

$(k+1)^p = 1 + pk + \frac{p(p-1)}{2}k^2 + \dots + pk^{p-1} + k^p$

Ta thấy rằng với $1 \le i \le p-1$, các hệ số $\binom{p}{i} = \frac{p!}{i!(p-i)!}$ đều chia hết cho $p$ vì $p$ là số nguyên tố và $i!(p-i)!$ không chia hết cho $p$. Do đó:

$(k+1)^p \equiv 1 + k^p \pmod{p}$

Áp dụng định lý Fermat mở rộng (một hệ quả của định lý nhị thức Newton và đồng dư thức):

$(k+1)^p \equiv k^p + 1 \pmod{p}$

Theo giả thiết quy nạp, ta có $k^{p-1} \equiv 1 \pmod{p}$. Nhân cả hai vế với $k$, ta được:

$k^p \equiv k \pmod{p}$

Do đó,

$(k+1)^p \equiv k + 1 \pmod{p}$

Mặt khác, ta có thể viết lại:

$(k+1)^p \equiv (k+1) \pmod p$ $(k+1)^p \equiv k^p+1 \pmod p$

Suy ra: $(k+1)^{p-1}(k+1) \equiv k^p + 1 \pmod p$

Theo giả thiết $k^{p-1} \equiv 1 \pmod p$, ta có $1*(k+1) \equiv k^p+1\pmod p$ $k+1 \equiv k^p+1\pmod p$ $k \equiv k^p \pmod p$

Chia cả hai vế cho k, ta được $1 \equiv k^{p-1}\pmod p$

Vậy định lý cũng đúng với $a = k+1$.

Theo nguyên lý quy nạp toán học, định lý Fermat nhỏ đúng với mọi số nguyên dương $a$ không chia hết cho $p$.

II. HỆ QUẢ

Hệ quả 1: Cho $p$ là một số nguyên tố và $a$ là một số nguyên bất kỳ. Khi đó:

$a^p \equiv a \pmod{p}$

Chứng minh:

• Nếu $a$ không chia hết cho $p$, theo định lý nhỏ Fermat, ta có $a^{p-1} \equiv 1 \pmod{p}$. Nhân cả hai vế với $a$, ta được $a^p \equiv a \pmod{p}$.
• Nếu $a$ chia hết cho $p$, thì $a \equiv 0 \pmod{p}$. Do đó, $a^p \equiv 0 \equiv a \pmod{p}$.

Vậy hệ quả 1 đúng với mọi số nguyên $a$.

Hệ quả 2: Nếu $a$ và $b$ là hai số nguyên thỏa mãn $a \equiv b \pmod{\phi(n)}$ thì $x^a \equiv x^b \pmod n$, với mọi số nguyên x và n là số nguyên tố cùng nhau. Trong đó $\phi(n)$ là hàm Euler.

III. ỨNG DỤNG TÍNH SỐ DƯ

Định lý nhỏ Fermat là một công cụ hữu ích để tìm số dư trong phép chia một lũy thừa cho một số nguyên tố.

Ví dụ 1: Tìm số dư của $2^{100}$ khi chia cho 7.

Giải:

Vì 7 là số nguyên tố và 2 không chia hết cho 7, theo định lý nhỏ Fermat, ta có:

$2^{7-1} \equiv 2^6 \equiv 1 \pmod{7}$

Ta có:

$2^{100} = 2^{6 \cdot 16 + 4} = (2^6)^{16} \cdot 2^4$

Do đó:

$2^{100} \equiv (1)^{16} \cdot 2^4 \equiv 16 \equiv 2 \pmod{7}$

Vậy số dư của $2^{100}$ khi chia cho 7 là 2.

Ví dụ 2: Tìm số dư của $3^{2023}$ khi chia cho 11.

Giải:

Vì 11 là số nguyên tố và 3 không chia hết cho 11, theo định lý nhỏ Fermat, ta có:

$3^{11-1} \equiv 3^{10} \equiv 1 \pmod{11}$

Ta có:

$2023 = 10 \cdot 202 + 3$

Do đó:

$3^{2023} = 3^{10 \cdot 202 + 3} = (3^{10})^{202} \cdot 3^3$

Vậy: $3^{2023} \equiv (1)^{202} \cdot 3^3 \equiv 27 \equiv 5 \pmod{11}$

Vậy số dư của $3^{2023}$ khi chia cho 11 là 5.

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

Giải: Ta có 13 là số nguyên tố, 7 không chia hết cho 13. Theo định lý Fermat nhỏ, $7^{12}\equiv 1\pmod{13}$. Ta có $2024 = 12 \cdot 168 + 8$. Do đó $7^{2024} = 7^{12 \cdot 168 + 8} = (7^{12})^{168} \cdot 7^8$. Ta có $7^{2024} \equiv (1)^{168} \cdot 7^8 \equiv 7^8 \pmod{13}$. $7^2 = 49 \equiv 10 \pmod{13}$ $7^4 \equiv 10^2 = 100 \equiv 9 \pmod{13}$ $7^8 \equiv 9^2 = 81 \equiv 3 \pmod{13}$ Vậy số dư khi chia $7^{2024}$ cho 13 là 3.

IV. BÀI TẬP ỨNG DỤNG

1. Tìm số dư của $5^{100}$ khi chia cho 13.
2. Tìm số dư của $2^{1000}$ khi chia cho 17.
3. Tìm số dư của $3^{1001}$ khi chia cho 101.
4. Chứng minh rằng $n^5 - n$ chia hết cho 30 với mọi số nguyên $n$.
5. Chứng minh rằng $a^{12} \equiv 1 \pmod{13}$ với mọi số nguyên $a$ không chia hết cho 13.
6. Tìm số dư khi chia $2^{2024} + 3^{2024}$ cho 5.
7. Tìm số dư khi chia $2023^{2024}$ cho 7.
8. Tìm số dư khi chia $17^{2023}$ cho 19.
9. Chứng minh $a^{p}-a$ chia hết cho p.
10. Tìm số dư khi chia $3^{2022}$ cho 10.

V. TÍNH CHẤT SỐ DƯ

1. 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. 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}$.

3. Tính chất lũy thừa

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

4. Tính chất chia hết

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

5. Tính chất module của tích

• $(a \cdot b) \pmod{m} = ((a \pmod{m}) \cdot (b \pmod{m})) \pmod{m}$

6. Tính chất module của tổng

• $(a + b) \pmod{m} = ((a \pmod{m}) + (b \pmod{m})) \pmod{m}$

7. Ví dụ

Ví dụ 1: Tìm số dư của $123 \cdot 456$ khi chia cho 7.

Giải:

• $123 \equiv 4 \pmod{7}$
• $456 \equiv 1 \pmod{7}$

Sử dụng tính chất nhân: $123 \cdot 456 \equiv 4 \cdot 1 \equiv 4 \pmod{7}$ Vậy số dư là 4.

Ví dụ 2: Tìm số dư của $2^{10} + 3^{10}$ khi chia cho 5.

Giải:

• $2^2 \equiv 4 \pmod{5}$

• $2^4 \equiv 16 \equiv 1 \pmod{5}$

• $2^{10} = (2^4)^2 \cdot 2^2 \equiv 1^2 \cdot 4 \equiv 4 \pmod{5}$

• $3^2 \equiv 9 \equiv 4 \pmod{5}$

• $3^4 \equiv 16 \equiv 1 \pmod{5}$

• $3^{10} = (3^4)^2 \cdot 3^2 \equiv 1^2 \cdot 4 \equiv 4 \pmod{5}$

Sử dụng tính chất cộng: $2^{10} + 3^{10} \equiv 4 + 4 \equiv 8 \equiv 3 \pmod{5}$ Vậy số dư là 3.

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

Giải: Ta có $2\equiv -1\pmod 3$, suy ra $2^{100} \equiv (-1)^{100}\equiv 1\pmod 3$. Vậy số dư cần tìm là 1.