威爾遜定理的Python簡單驗(yàn)證

王德貴

威爾遜定理是以英格蘭數(shù)學(xué)家愛德華·華林的學(xué)生約翰·威爾遜命名的，盡管這對師生未能給出證明。華林于1770年提出該定理，1773年由拉格朗日首次證明。威爾遜定理是判定一個自然數(shù)是否為素?cái)?shù)的充分必要條件，它也是數(shù)論四大定理（威爾遜定理、歐拉定理、孫子定理、費(fèi)馬小定理）之一。

今天我們就用Python來簡單地驗(yàn)證威爾遜定理及其逆定理。

18世紀(jì)中葉，約翰·威爾遜發(fā)現(xiàn)了一個極為罕見的關(guān)系：取從1到某個質(zhì)數(shù)所有連續(xù)正整數(shù)的乘積，例如從1乘到11，即11的階乘11！，除去11這個數(shù)，得10！。無疑10！不能被11整除。

然而，如果給10！加上1的話，1×2×3×4×5×6×7×8×9×10+1=3628801，怎么也不會想到，3628801卻能被11整除（3628801÷11=329891）。類似地，從1到質(zhì)數(shù)7的階乘7！中略去7，再加上1，得1×2×3×4×5×6+1=721，721也能被7整除（721÷7=103）。那么其他的質(zhì)數(shù)是不是也有這樣的規(guī)律呢？

威爾遜定理可以簡述為：

當(dāng)p為質(zhì)數(shù)時，（p-1）！+1能被p整除。

威爾遜定理逆定理可以簡述為：

若一個數(shù) （p-1）！+1 能被 p 整除，那么 p 為質(zhì)數(shù)。

威爾遜定理已經(jīng)被證明，今天我們只做簡單驗(yàn)證。

數(shù)論四大定理之中，我們驗(yàn)證了費(fèi)馬小定理。如果想了解更深入的知識，大家可以參考相關(guān)資料。今天我們利用Python只做簡單的驗(yàn)證。

我們?nèi)我廨斎胍粋€正整數(shù)p，驗(yàn)證（p-1）！+1 能被 p 整除，如果整除則p為質(zhì)數(shù)，否則為合數(shù)。當(dāng)然我們也知道，如果輸入的p是質(zhì)數(shù)，（p-1）！+1 一定能被 p 整除。這樣就驗(yàn)證了威爾遜定理和逆定理。

階乘問題，我們用自定義函數(shù)計(jì)算出結(jié)果，然后加上1賦值給變量m保存然后我們判斷m是否能被 p 整除，如果能整除，則p為質(zhì)數(shù)，否則為合數(shù)。

范圍驗(yàn)證即輸入一個范圍，依次驗(yàn)證這個范圍內(nèi)的整數(shù)是否為質(zhì)數(shù)，如果是質(zhì)數(shù)則添加到質(zhì)數(shù)列表中，最后顯示出來。這也是獲得一定范圍內(nèi)質(zhì)數(shù)的又一種方法。

根據(jù)前面的設(shè)計(jì)和分析，編寫程序。

程序設(shè)計(jì)涉及的是等級考試的自定義函數(shù)（四級內(nèi)容），如果不用自定義函數(shù)，則只涉及程序結(jié)構(gòu)知識點(diǎn)，屬于二級內(nèi)容。

1.驗(yàn)證：即輸入單個數(shù)據(jù)的驗(yàn)證

（1）二級考試內(nèi)容：涉及程序設(shè)計(jì)的三種結(jié)構(gòu)（圖1）

（2）四級考試內(nèi)容：利用自定義函數(shù)（圖2）

兩個程序運(yùn)行結(jié)果相同：（圖3）

2.范圍：即在一定范圍內(nèi)驗(yàn)證威爾遜定理及其逆定理

（1）用二級考試內(nèi)容“循環(huán)”來驗(yàn)證。（圖4）

（2）用四級考試內(nèi)容“遞推-自定義函數(shù)”來驗(yàn)證。（圖5）

（3）用四級考試內(nèi)容“遞歸-自定義函數(shù)”來驗(yàn)證。（圖6）

三個程序的驗(yàn)證結(jié)果是一樣的。（圖7）

威爾遜定理及其逆定理的驗(yàn)證測試，可以驗(yàn)證一個正整數(shù)，也可以驗(yàn)證一定范圍內(nèi)的所有正整數(shù)，這種方法也可以得到一定范圍內(nèi)的所有質(zhì)數(shù)。

需要注意的是，如果階乘運(yùn)算使用了遞歸，則需要注意遞歸深度的限制。

有關(guān)威爾遜定理及數(shù)論四大定理問題，有興趣的同學(xué)可以參考相關(guān)資料，本文不作詳細(xì)介紹。如有不當(dāng)之處，請各位同仁、朋友斧正。