費馬於1636年發現了這個定理。在一封1640年10月18日的信中他第一次使用了上面的書寫方式。

　　費馬對梅森說:“我發現了費馬小定理，這個可以用來檢驗素數。”

　　梅森說:“我知道，一個數字是一個素數減一次方除以這個素數，余數一定可以得到1。”

　　費馬說:“比如2的100次方除以13得到的余數是幾?根據費馬小定理公式計算，得到就是3.”

　　梅森說:“那你如何進行素數檢驗?”

　　費馬說:“利用隨機化算法判斷一個數是合數還是可能是素數。”

　　梅森說:“怎麽個隨機法?”

　　費馬說:“根據我的辦法，想要判斷一個數n是不是素數，隨機選取一個比n小的數a，得出這個a的n減去一次方，然後除以這個數，是不是會余1.”

　　梅森感覺有些繞，問:“然後呢?”

　　費馬說:“如果余數不是1，就說明一定是合數。”

　　梅森搖搖頭說:“如果余數是1，也許是個合數呢?你這個不嚴謹啊。”

　　費馬說:“沒錯，如果選取了很多個小數余數都等於1。”

　　梅森搖搖頭說:“那也不見得一定是素數。”

　　費馬說:“如果不是素數，那也可以稱之為偽素數。”

　　梅森搖搖頭說:“這只能確定一定是不是合數，卻不敢肯定一定是素數，只能知道是不是偽素數。”