費馬小定理的Python簡單驗證

王德貴

我們在往期利用Python驗證過費馬大定理，這是數學史上關于數論的經典問題，其實費馬小定理也一樣享譽數學界，它是初等數論四大定理之一。

今天我們就用Python來簡單地驗證費馬小定理。

在1636年提出的費馬小定理是數論中的一個重要定理。它是初等數論四大定理之一：威爾遜定理、歐拉定理（數論中的歐拉定理）、中國剩余定理（又稱孫子定理）、費馬小定理。在初等數論中有著非常廣泛和重要的應用。實際上，它是歐拉定理的一個特殊情況。

費馬小定理可以簡述為：

如果p是一個質數，而整數a不是p的倍數，則有a的（p-1）次冪除以p余1。

數學表達式為：

假如p是質數，且（a，p）=1，那么 a^（p-1） ≡1（mod p）

還有另一種寫法：

假如p是質數，a為整數，那么 a^p ≡a（mod p）

此處三橫線為恒等號。有關費馬小定理的相關知識這里不做介紹，有興趣的朋友可以自己去學習，費馬小定理已經被證明，今天我們只做簡單驗證。

我看到這個定理內容，就想到了勾股數，想用Python驗證勾股數的方法，來驗證費馬小定理。

如果想了解更深入的知識，大家可以參考相關資料。今天我們利用Python只做簡單的驗證。

驗證的范圍越大，冪次越高，時間復雜度會幾何級數增大，大家可以自行測試。

程序設計不是很難，是等級考試二級內容，而自定義函數是四級內容。

首先生成p范圍內的質數列表，并判斷p是否為質數。如果不是質數，則重新輸入，如果是質數，則提示輸入a，如果a與p互質，則提示費馬小定理成立，運行結果如下。

如果a是p的倍數，則余數為0，即可以整除p，這個比較好理解。

運行結果：

費馬小定理的另一種形式，我們也來驗證一下，程序設計如下?；舅悸愤€是先生成p范圍內的所有質數列表，然后判斷p是否為質數。

如果p不是質數，重新輸入p值。如果p是質數，則提示輸入任意整數a，然后進行驗證，計算并輸出結果。

定理的驗證測試，多輸入幾個值，就可以了。也可以在一定范圍內驗證。

比如，輸入一個質數p，讓a在一定范圍內驗證即可。程序如下。

輸入p為質數，再提示輸入a的最小值和最大值，然后進行逐一驗證，并輸出結果。

在輸入范圍30-40時，依次驗證，a與p互質時，費馬小定理均成立，而當a=34時，a是p的倍數，余數為0。

費馬在提出定理時，還說明了a是一個素數的要求，但是這個要求實際上是不必要的。

從費馬小定理還引申了很多相關數論問題，有興趣的同學可以參考相關資料，本文不做介紹。如有不當之處，請各位同仁、朋友斧正。