費馬于1636年發(fā)現(xiàn)了這個定理。在一封1640年10月18日的信中他第一次使用了上面的書寫方式。
費馬對梅森說：“我發(fā)現(xiàn)了費馬小定理，這個可以用來檢驗素數(shù)?！?p> 梅森說：“我知道，一個數(shù)字是一個素數(shù)減一次方除以這個素數(shù)，余數(shù)一定可以得到1?！?p> 費馬說：“比如2的100次方除以13得到的余數(shù)是幾？根據(jù)費馬小定理公式計算，得到就是3.”
梅森說：“那你如何進行素數(shù)檢驗？”
費馬說：“利用隨機化算法判斷一個數(shù)是合數(shù)還是可能是素數(shù)?！?p> 梅森說：“怎么個隨機法？”
費馬說：“根據(jù)我的辦法，想要判斷一個數(shù)n是不是素數(shù)，隨機選取一個比n小的數(shù)a，得出這個a的n減去一次方，然后除以這個數(shù)，是不是會余1.”
梅森感覺有些繞，問：“然后呢？”
費馬說：“如果余數(shù)不是1，就說明一定是合數(shù)?！?p> 梅森搖搖頭說：“如果余數(shù)是1，也許是個合數(shù)呢？你這個不嚴謹啊?！?p> 費馬說：“沒錯，如果選取了很多個小數(shù)余數(shù)都等于1?！?p> 梅森搖搖頭說：“那也不見得一定是素數(shù)?！?p> 費馬說：“如果不是素數(shù)，那也可以稱之為偽素數(shù)?！?p> 梅森搖搖頭說：“這只能確定一定是不是合數(shù)，卻不敢肯定一定是素數(shù)，只能知道是不是偽素數(shù)?！?