Chứng minh định lý Fermat nhỏ: `a^Pequiva` (mod P) với a là số tự nhiên và P là số nguyên tố

Để chứng minh định lý Fermat nhỏ, ta cần chứng minh rằng nếu \( P \) là một số nguyên tố và \( a \) là một số nguyên tự nhiên không chia hết cho \( P \), thì:

\[ a^{P-1} \equiv 1 \,(\text{mod } P) \]

Chúng ta sẽ sử dụng một số ý tưởng từ lý thuyết số và được trình bày như sau:

1. Xét tập hợp các bội của a: Chúng ta xem xét các số \( a, 2a, 3a, \ldots, (P-1)a \). Tất cả các số này modulo \( P \) đều không trùng nhau (điều này xảy ra do nếu \( ka \equiv ma \,(\text{mod } P) \) với \( 1 \leq k, m < P \), thì \( P \) chia hết cho \( a(k - m) \), mà \( P \) là số nguyên tố không chia hết cho \( a \), do đó \( k \equiv m \)).

2. Tính tập hợp số modulo P: Cụ thể, các số \( a, 2a, 3a, \ldots, (P-1)a \) tạo thành một tập hợp gồm \( P-1 \) phần tử khác nhau. Theo lý thuyết số, tập hợp này sẽ tương ứng với các số nguyên từ 1 đến \( P-1 \) khi chia theo modulo \( P \).

3. Tính tích của các số trong tập hợp: Ta tính tích của toàn bộ các số trong tập hợp này:
\[
a \cdot 2a \cdot 3a \cdots (P-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (P-1) \,(\text{mod } P)
\]
Nghĩa là:
\[
a^{P-1} \cdot (P-1)! \equiv (P-1)! \,(\text{mod } P)
\]

4. Chia cả hai vế cho (P-1)!: Vì \( P \) là số nguyên tố và \( (P-1)! \) không chia hết cho \( P \) (theo định lý Wilson), ta có thể chia cả hai vế cho \( (P-1)! \):
\[
a^{P-1} \equiv 1 \,(\text{mod } P)
\]

Như vậy, ta đã chứng minh rằng \( a^{P-1} \equiv 1 \,(\text{mod } P) \) cho bất kỳ \( a \) nào không chia hết cho \( P \). Nếu \( a \) chia hết cho \( P \), thì hiển nhiên \( a^P \equiv 0 \,(\text{mod } P) \).

Tóm lại, định lý Fermat nhỏ khẳng định rằng nếu \( P \) là số nguyên tố và \( a \) là số tự nhiên không chia hết cho \( P \), thì \( a^{P-1} \equiv 1 \,(\text{mod } P) \), điều này đã được chứng minh qua việc xem xét các bội của \( a \) và tính toán modulo \( P \).