Định lý Fermat nhỏ

Tài liệu học tập: Định lý Fermat nhỏ

1. Giới thiệu

Định lý Fermat nhỏ là một trong những kết quả cơ bản và quan trọng trong lý thuyết số. Nó cung cấp một công cụ mạnh mẽ để giải quyết các bài toán liên quan đến số học, đặc biệt là các bài toán về phép chia và số dư. Tài liệu này sẽ trình bày chi tiết về định lý Fermat nhỏ, các ứng dụng và ví dụ minh họa.

2. Định lý Fermat nhỏ

Đị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}$

Phát biểu khác: Với $p$ là số nguyên tố và $a$ là số nguyên bất kỳ, ta có:

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

Giải thích:

• Ký hiệu "$\equiv \pmod{p}$" có nghĩa là đồng dư theo modulo $p$. Hai số nguyên $x$ và $y$ được gọi là đồng dư modulo $p$ nếu hiệu $x - y$ chia hết cho $p$, ký hiệu là $x \equiv y \pmod{p}$.
• Định lý Fermat nhỏ nói rằng nếu bạn lấy một số nguyên $a$, nâng lên lũy thừa $(p-1)$, rồi chia cho số nguyên tố $p$ (với điều kiện $a$ không chia hết cho $p$), thì số dư sẽ luôn là 1.

3. Chứng minh Định lý Fermat nhỏ

Có nhiều cách chứng minh định lý Fermat nhỏ. Dưới đây là một trong những cách chứng minh phổ biến nhất, sử dụng phương pháp quy nạp và tính chất của hệ thặng dư.

Chứng minh:

Xét tập hợp $S = \{1, 2, 3, ..., p-1\}$. Vì $p$ là số nguyên tố nên các phần tử của $S$ đều không chia hết cho $p$.

Nhân mỗi phần tử của $S$ với $a$, ta được tập hợp $aS = \{a, 2a, 3a, ..., (p-1)a\}$.

Bước 1: Chứng minh các phần tử của $aS$ đôi một không đồng dư modulo $p$.

Giả sử tồn tại $ia$ và $ja$ sao cho $ia \equiv ja \pmod{p}$ với $1 \leq i < j \leq p-1$. Khi đó, $(j-i)a \equiv 0 \pmod{p}$. Vì $a$ không chia hết cho $p$ và $0 < j - i < p$, suy ra $j - i$ không chia hết cho $p$. Điều này mâu thuẫn với $(j-i)a \equiv 0 \pmod{p}$. Vậy các phần tử của $aS$ đôi một không đồng dư modulo $p$.

Bước 2: Chứng minh tập hợp số dư của các phần tử trong $aS$ khi chia cho $p$ là $\{1, 2, 3, ..., p-1\}$.

Vì có $p-1$ phần tử trong $aS$ và chúng đôi một không đồng dư modulo $p$, nên các số dư của chúng khi chia cho $p$ phải là $p-1$ số khác nhau. Hơn nữa, các số dư này đều thuộc tập hợp $\{1, 2, 3, ..., p-1\}$. Vậy tập hợp số dư của các phần tử trong $aS$ khi chia cho $p$ chính là $\{1, 2, 3, ..., p-1\}$.

Bước 3: Từ Bước 2, ta có:

$a \cdot 2a \cdot 3a \cdot ... \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1) \pmod{p}$

$a^{p-1}(1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1)) \equiv 1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1) \pmod{p}$

$a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}$

Vì $(p-1)!$ không chia hết cho $p$, ta có thể chia cả hai vế cho $(p-1)!$:

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

Vậy định lý Fermat nhỏ được chứng minh.

4. Ứng dụng của Định lý Fermat nhỏ

Định lý Fermat nhỏ có nhiều ứng dụng trong giải toán, đặc biệt là trong các bài toán về đồng dư và tìm số dư của một phép chia.

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

Giải:

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

$2^{101-1} \equiv 2^{100} \equiv 1 \pmod{101}$

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

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

Giải:

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

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

Ta có $1000 = 6 \cdot 166 + 4$, vậy:

$3^{1000} = 3^{6 \cdot 166 + 4} = (3^6)^{166} \cdot 3^4$

Do đó:

$3^{1000} \equiv (3^6)^{166} \cdot 3^4 \equiv 1^{166} \cdot 3^4 \equiv 3^4 \equiv 81 \equiv 4 \pmod{7}$

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

Ví dụ 3: Chứng minh rằng $n^5 - n$ chia hết cho 30 với mọi số nguyên $n$.

Giải:

Ta cần chứng minh $n^5 - n$ chia hết cho 2, 3 và 5 (vì 30 = 2 * 3 * 5).

• Chia hết cho 2: $n^5 - n = n(n^4 - 1)$. Nếu $n$ chẵn thì $n^5 - n$ chẵn. Nếu $n$ lẻ thì $n^4$ lẻ, $n^4 - 1$ chẵn, vậy $n^5 - n$ chẵn. Do đó $n^5 - n$ chia hết cho 2.

• Chia hết cho 3: Theo định lý Fermat nhỏ, $n^3 \equiv n \pmod{3}$. Vậy $n^5 \equiv n^3 \cdot n^2 \equiv n \cdot n^2 \equiv n^3 \equiv n \pmod{3}$. Do đó $n^5 - n \equiv 0 \pmod{3}$, hay $n^5 - n$ chia hết cho 3.

• Chia hết cho 5: Theo định lý Fermat nhỏ, $n^5 \equiv n \pmod{5}$. Vậy $n^5 - n \equiv 0 \pmod{5}$, hay $n^5 - n$ chia hết cho 5.

Vì $n^5 - n$ chia hết cho 2, 3 và 5, nên $n^5 - n$ chia hết cho 30.

5. Bài tập vận dụng

1. Tìm số dư của $5^{100}$ khi chia cho 7.
2. Tìm số dư của $7^{2023}$ khi chia cho 11.
3. Chứng minh rằng $n^{13} - n$ chia hết cho 2730 với mọi số nguyên $n$. (Gợi ý: 2730 = 2 * 3 * 5 * 7 * 13)
4. Tìm số dư của $2^{100000}$ khi chia cho 17.
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. Kết luận

Định lý Fermat nhỏ là một công cụ hữu ích trong lý thuyết số và có nhiều ứng dụng trong giải toán. Việc nắm vững định lý này và các ứng dụng của nó sẽ giúp bạn giải quyết các bài toán đồng dư một cách hiệu quả. Hãy luyện tập thêm các bài tập để củng cố kiến thức và kỹ năng giải toán.