費馬小定理,我的理解

觸碰標題下面一行的「邵勇老師」查看所有文章；觸碰「數學教學研究」, 關注本微信公眾號(sx100sy)。本公眾號內容均由邵勇本人獨創，歡迎轉發，但未經許可不能轉載。特別聲明，本人未曾授權任何網站（包括微博）和公眾號轉載邵勇「數學教學研究」公眾號的內容。每周推送兩到三篇內容上有份量的數學文章，但在行文上力爭做到深入淺出。幾分鐘便可讀完，輕鬆學數學。 

費馬小定理

[ p是英語 prime number（素數）的首字母 ；n是 number 的首字母 ] 。

(2) 還是對素數p=5，這裡取n=3，則有

(3) 對素數p=3和正整數n=4，有

您可以繼續，隨便取素數p和正整數n，對費馬小定理進行驗證。建議以兩種方式取值：一種是取定一個素數p，讓n取更多的自然數；另一種是n先取定，讓p取更多的素數。下面給出費馬小定理的嚴格證明。真的一點兒都不難，我們都可以看懂。

它的右端一共有p+1項。除兩頭的兩項外，中間p－1項的二項式係數中都有因子p。我們就來考慮這p－1項。它們的分母中都有m!，分別是1!，2!，3!，...，(p－1)!  。顯然，不管是哪一項中的階乘，其中的每個因子都小於素數p。所以，每一項中分子上的p都不能被這一項分母中的因子約分掉。所以，這p－1項的係數中都有因子p，也就都能夠被p整除。所以這p－1項的和也就可以被p整除：

（注意，我們特別把這個式子單獨寫出來，是因為後面我們要用到它。）

我用大括號把上式中的各項進行分組，得到

若假設上式右邊第一個中括號中的式子n^p－n能夠被p整除，則由於上式右邊第二個中括號中的式子我們前面已說過能被p整除，所以上式左邊的式子 (n+1)^p－(n+1)也就能夠被p整除。
這說明，對任意取定的素數p，若對正整數n，有n^p－n能夠被p整除，則對(n+1)來說，有(n+1)^p－(n+1)也能夠被p整除。這讓我想到了數學歸納法。於是我們只需證明對n=1，有n^p－n能被p整除。這是顯然的，因為這時n^p－n=0，而0當然能被p整除。於是，根據數學歸納法，費馬小定理得以證明。我們下面特別說一說n=2的情況。這時的費馬小定理成為：若p是素數，則2^p－2能被p整除。據某書上說，費馬小定理n=2時的情況，早在公元前500年左右就被中國人所知曉。這本書非中國人所寫，我看到的是中譯本。不知作者所說是否有依據。據我所知，我們提到中國數學家的成就時，好象沒有人提及這個與素數相關的發現。不知您是否了解一些。有關數學史，本文和本公眾號一般很少涉及，因為我不是研究數學史的專家。不是某方面的專家，在這方面一張口很容易出錯。但中國對世界數學的貢獻確實是很大的。

下面說一說費馬小定理的另一種形式：若p是素數，n為不能被p整除的正整數，則

費馬小定理是說如果一個數是素數，則n^p－n能夠被p整除。它的逆否命題同樣成立：如果一個數不能整除n^p－n，則這個數不是素數（是合數）。我們知道一共有四種命題：原命題，逆命題，否命題和逆否命題。原命題成立，逆否命題一定成立。但逆命題和否命題不一定成立。很有可能你隨便選擇一個正整數，它能夠被n^p－n整除，但它不是素數，而是合數。這就說明逆命題不成立。同樣地，一個數不是素數，但它也可以被n^p－n整除。這說明否命題也是不成立的。上面是用命題來說明費馬小定理。我們還可以從集合的觀點說明費馬小定理：正整數集合可以劃分成三個互不相交的集合的併集，第一個集合是素數集合，它的元素都可以整除n^p－n。第二個集合由無窮多的合數構成，它的每一個元素都不能整除n^p－n。第三個集合由無窮多的合數構成，但這些合數都能夠整除n^p－n。費馬小定理可以用來發現一個數不是素數（而是合數），如果這個數不能整除n^p－n。這就是所謂的費馬素性檢驗。用費馬小定理不能確定一個通過素性檢驗的數是否是素數，它的「功能」沒有上一期所講的帕斯卡三角形方法那麼強。但帕斯卡三角形方法運算量巨大。費馬素性檢驗的運算量就很少，但還需要想辦法改進（已有人做到，這裡不細說，太艱深了）。