費馬小定理的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，這個比較好理解。……