費(fèi)馬小定理的Python簡(jiǎn)單驗(yàn)證

王德貴

我們?cè)谕诶肞ython驗(yàn)證過費(fèi)馬大定理，這是數(shù)學(xué)史上關(guān)于數(shù)論的經(jīng)典問題，其實(shí)費(fèi)馬小定理也一樣享譽(yù)數(shù)學(xué)界，它是初等數(shù)論四大定理之一。

今天我們就用Python來簡(jiǎn)單地驗(yàn)證費(fèi)馬小定理。

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

費(fèi)馬小定理可以簡(jiǎn)述為：

如果p是一個(gè)質(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）

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

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

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

驗(yàn)證的范圍越大，冪次越高，時(shí)間復(fù)雜度會(huì)幾何級(jí)數(shù)增大，大家可以自行測(cè)試。

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

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

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

運(yùn)行結(jié)果：

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

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

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

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

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

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

費(fèi)馬在提出定理時(shí)，還說明了a是一個(gè)素?cái)?shù)的要求，但是這個(gè)要求實(shí)際上是不必要的。

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