王德貴

我們在往期利用Python驗證過費馬大定理，這是數(shù)學(xué)史上關(guān)于數(shù)論的經(jīng)典問題，其實費馬小定理也一樣享譽數(shù)學(xué)界，它是初等數(shù)論四大定理之一。

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

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

費馬小定理可以簡述為：

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

數(shù)學(xué)表達(dá)式為：

假如p是質(zhì)數(shù)，且（a，p）=1，那么 a^（p-1） ≡1（mod p）

還有另一種寫法：

假如p是質(zhì)數(shù)，a為整數(shù)，那么 a^p ≡a（mod p）

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

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

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

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

程序設(shè)計不是很難，是等級考試二級內(nèi)容，而自定義函數(shù)是四級內(nèi)容。

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

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

運行結(jié)果：

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

如果p不是質(zhì)數(shù)，重新輸入p值。如果p是質(zhì)數(shù)，則提示輸入任意整數(shù)a，然后進(jìn)行驗證，計算并輸出結(jié)果。

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

比如，輸入一個質(zhì)數(shù)p，讓a在一定范圍內(nèi)驗證即可。程序如下。

輸入p為質(zhì)數(shù)，再提示輸入a的最小值和最大值，然后進(jìn)行逐一驗證，并輸出結(jié)果。

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

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

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