Định lý Fermat nhỏ

Định lý Fermat nhỏ (hay còn gọi là định lý Fermat cơ bản, khác với định lý Fermat lớn) khẳng định rằng nếu $p$ là một số nguyên tố, thì với bất kỳ số nguyên $a$, $a^p-<!--\; -\; -->a$ sẽ chia hết cho $p$. Nói cách khác, chúng ta có thể viết:

$a^p\equiv <!--\; \equiv \; -->a\left(\mathrm{mod}p\right)$

Ví dụ: nếu $a=3,p=5⟹<!--\; ⟹\; -->3^5-<!--\; -\; -->3=240\equiv <!--\; \equiv \; -->0\left(\mathrm{mod}5\right)$.

Một cách khác để phát biểu định lý là: nếu $p$ là một số nguyên tố và $a$ là một số nguyên không chia hết cho $p$, thì $a^{p-<!--\; -\; -->1}-<!--\; -\; -->1$ sẽ chia hết cho $p$. Tức là:

$a^{p-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1\left(\mathrm{mod}p\right)$

Ví dụ: nếu $a=4,p=5⟹<!--\; ⟹\; -->4^{5-<!--\; -\; -->1}-<!--\; -\; -->1=255\equiv <!--\; \equiv \; -->0\left(\mathrm{mod}5\right)$

Một cách diễn giải khác là: 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}-<!--\; -\; -->1$ chia hết cho $p$.

Định lý Fermat nhỏ là nền tảng cho các phương pháp kiểm tra tính nguyên tố xác suất trong bài kiểm tra Fermat, đồng thời là một trong những định lý cơ bản của lý thuyết số học.

Tiểu sử

Pierre de Fermat là người đầu tiên đưa ra định lý này trong một bức thư gửi ngày 18 tháng 10 năm 1640 cho người bạn tri kỷ Frénicle de Bessy. Quan điểm của ông có thể được diễn đạt như sau:

Nếu $p$ là một số nguyên tố và $a$ là một số nguyên không chia hết cho $p$, thì $a^{}$

p − 1 − 1 {\displaystyle a^{p-1}-1} sẽ chia hết cho $p$.

Trên thực tế, định lý được phát biểu như sau:

Mỗi số nguyên tố luôn đo được một trong các số mũ – 1 của bất kỳ cấp số cộng nào, và số mũ của cấp số đó là bội số của số nguyên tố trừ 1; sau khi xác định được số mũ đầu tiên thỏa mãn, tất cả các số mũ là bội số của số mũ đầu tiên cũng thỏa mãn điều kiện này.

Như thường lệ, Fermat không đưa ra bằng chứng cho định lý này mà chỉ thông báo về nó:

Và mệnh đề này thường đúng với tất cả các cấp số cộng và mọi số nguyên tố; nếu không sợ phải dài dòng, tôi đã gửi cho bạn bằng chứng của nó.

(Và mệnh đề này thường đúng cho tất cả các dãy số và tất cả các số nguyên tố; tôi đã sẵn sàng gửi cho bạn chứng minh nếu không lo lắng về việc sẽ quá dài dòng.) (Tạm dịch: Mệnh đề này đúng với mọi dãy số và mọi số nguyên tố; nếu không vì chứng minh quá dài, tôi đã gửi cho bạn rồi.)

Euler là người đầu tiên công bố một bằng chứng vào năm 1736 trong bài viết mang tên 'Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio' trên tờ Proceedings của Viện St. Petersburg, nhưng Leibniz đã có một chứng minh tương tự trong bản thảo chưa công bố vào khoảng trước năm 1683.

Tên gọi 'định lý nhỏ của Fermat' lần đầu tiên xuất hiện vào năm 1913 trong tác phẩm Zahlentheorie của Kurt Hensel:

Trong mọi nhóm hữu hạn, có một định lý cơ bản thường được gọi là định lý nhỏ của Fermat, vì một phần đặc biệt của định lý này đã được Fermat chứng minh đầu tiên.

(Có một định lý cơ bản áp dụng cho mọi nhóm hữu hạn, thường được gọi là định lý nhỏ của Fermat vì Fermat là người đầu tiên chứng minh một phần rất đặc biệt của định lý này.) (Tạm dịch: Có một định lý cơ bản trong mọi nhóm hữu hạn, thường được gọi là định lý nhỏ của Fermat vì Fermat là người đầu tiên chứng minh được một phần rất đặc biệt của nó.)

Lịch sử sâu hơn

Các nhà toán học Trung Quốc cũng đã độc lập đưa ra một giả thuyết (gọi là giả thuyết Trung Quốc) rằng nếu $p$ là số nguyên tố, thì $2^p\equiv <!--\; \equiv \; -->2\left(\mathrm{mod}p\right)$. Điều này là một trường hợp đặc biệt của định lý nhỏ của Fermat. Tuy nhiên, điều ngược lại (nếu $2^p\equiv <!--\; \equiv \; -->2\left(\mathrm{mod}p\right)$ thì $p$ là số nguyên tố) không đúng. Ví dụ, $2^{341}\equiv <!--\; \equiv \; -->2\left(\mathrm{mod}341\right)$, nhưng $341=11\times <!--\; \times \; -->31$ là hợp số (được gọi là số giả nguyên tố [pseudoprime]).

Chứng minh

Nếu $(a,p)\ne <!--\; \ne \; -->1$ thì rõ ràng $a^p\equiv <!--\; \equiv \; -->a\equiv <!--\; \equiv \; -->0\left(\mathrm{mod}p\right)$.

Nếu $(a,p)=1$,

liệt kê các bội số của $p-<!--\; -\; -->1$ nhân với $a$:

$a,2a,3a,...,(p-<!--\; -\; -->1)a$, tất cả các số này đều phải nguyên tố cùng nhau với p

Giả sử có tồn tại: $na\equiv <!--\; \equiv \; -->ma\left(\mathrm{mod}p\right)$, với $p-<!--\; -\; -->1\ge <!--\; \ge \; -->n>m\ge <!--\; \ge \; -->1$,

$a(n-<!--\; -\; -->m)\equiv <!--\; \equiv \; -->0\left(\mathrm{mod}p\right)\Rightarrow <!--\; \Rightarrow \; -->n-<!--\; -\; -->m\equiv <!--\; \equiv \; -->0\left(\mathrm{mod}p\right)$.

do việc chọn m,n như vậy là không thể xảy ra,

do đó các số $na(n=1,2,...,p-<!--\; -\; -->1)$ sẽ tạo thành hệ thống thặng dư thu gọn modulo p

Khi nhân các số lại với nhau, ta có:

$a\times <!--\; \times \; -->2a\times <!--\; \times \; -->3a\times <!--\; \times \; -->...\times <!--\; \times \; -->(p-<!--\; -\; -->1)a\equiv <!--\; \equiv \; -->(p-<!--\; -\; -->1)!\left(\mathrm{mod}p\right)$.

Hoặc

$a^{p-<!--\; -\; -->1}\times <!--\; \times \; -->(p-<!--\; -\; -->1)!\equiv <!--\; \equiv \; -->(p-<!--\; -\; -->1)!\left(\mathrm{mod}p\right)⟹<!--\; ⟹\; -->a^{p-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1\left(\mathrm{mod}p\right)\Rightarrow <!--\; \Rightarrow \; -->a^p\equiv <!--\; \equiv \; -->a\left(\mathrm{mod}p\right)$ $\mathrm{◻<!--\; ◻\; -->}$

Fermat đã nêu định lý nhưng chưa chứng minh. Đã có nhiều cách chứng minh định lý này, thường sử dụng hệ quả từ định lý Euler.

Mở rộng

Một phiên bản mở rộng của định lý này là: nếu p là số nguyên tố và m cùng n là các số nguyên dương thỏa mãn $m\equiv <!--\; \equiv \; -->n(\mathrm{mod}p-<!--\; -\; -->1)$, thì với mọi .

Định lý Fermat có thể được mở rộng qua Định lý Euler: với bất kỳ modulo n và số nguyên a mà a và n là các số nguyên tố cùng nhau, ta có

$a^{\mathrm{\phi <!--\; \phi \; -->}\left(n\right)}\equiv <!--\; \equiv \; -->1\left(\mathrm{mod}n\right)$

Trong đó, φ(n) là ký hiệu hàm Euler, dùng để đếm số lượng số nguyên từ 1 đến n mà nguyên tố cùng nhau với n. Định lý này mở rộng định lý nhỏ Fermat, vì khi n = p là số nguyên tố, φ(p) = p − 1.

Một sự mở rộng còn rộng hơn nữa là Định lý Carmichael.

Một biến thể khác của định lý này có thể được tìm thấy trong các trường hữu hạn.

Hệ quả đảo

Đảo luận về định lý nhỏ Fermat cho thấy rằng luận điểm đảo của nó không chính xác, đặc biệt là với các số Carmichael. Tuy nhiên, một phiên bản chính xác hơn được gọi là định lý Lehmer có thể khắc phục điều này. Định lý Lehmer được phát biểu như sau:

Nếu có một số nguyên a sao cho

$a^{p-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1\left(\mathrm{mod}p\right)$

và với mọi số nguyên tố q là ước của p − 1 thì

$a^{(p-<!--\; -\; -->1)/q}\not\equiv 1\left(\mathrm{mod}p\right)$,

thì p là một số nguyên tố.

Định lý này là cơ sở cho phương pháp kiểm tra tính nguyên tố Lucas–Lehmer, một công cụ quan trọng trong việc xác định tính nguyên tố.

Số giả nguyên tố

Khi p là một hợp số và tồn tại một số nguyên a sao cho $a^{p-<!--\; -\; -->1}-<!--\; -\; -->1$ chia hết cho p, thì p được gọi là số giả nguyên tố cơ sở a. F. Sarrmus đã phát hiện số giả nguyên tố đầu tiên là 341 = 11×31 vào năm 1820, với cơ số 2.

Một số p được gọi là số Carmichael nếu nó là số giả nguyên tố với cơ số a cho mọi a mà (a, p) = 1 (ví dụ như 561).

• Định lý cuối cùng của Fermat
• Thương số Fermat

Các liên kết tham khảo

• Định lý của Fermat tại Encyclopædia Britannica (tiếng Anh)
• Định lý nhỏ của Fermat
• Hàm và Định lý Euler
• Định lý nhỏ của Fermat và Chứng minh của Sophie
• Vườn Toán: modulo - Phần 5