歐拉定理的Python簡單驗(yàn)證

王德貴

在數(shù)論中，歐拉定理（Euler Theorem），也稱費(fèi)馬-歐拉定理或歐拉函數(shù)定理，是一個(gè)關(guān)于同余性質(zhì)的定理，它也是數(shù)論四大定理（威爾遜定理、費(fèi)馬小定理、孫子定理、歐拉定理）之一。

數(shù)學(xué)史上公認(rèn)的4名最偉大的數(shù)學(xué)家分別是：阿基米德、牛頓、歐拉和高斯。阿基米德有“撬起地球”的豪言壯語，牛頓因?yàn)樘O果聞名世界，高斯少年時(shí)就顯露出計(jì)算天賦，唯獨(dú)歐拉沒有戲劇性的故事卻讓人印象深刻。

然而，幾乎每一個(gè)數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字——初等幾何的歐拉線、多面體的歐拉定理、立體解析幾何的歐拉變換公式、數(shù)論的歐拉函數(shù)、變分法的歐拉方程、復(fù)變函數(shù)的歐拉公式……歐拉還是數(shù)學(xué)史上最多產(chǎn)的數(shù)學(xué)家，他一生寫下886本書籍論文，平均每年寫出800多頁，彼得堡科學(xué)院為了整理他的著作，足足忙碌了47年。他的著作《無窮小分析引論》《微分學(xué)》《積分學(xué)》是18世紀(jì)歐洲標(biāo)準(zhǔn)的微積分教科書。歐拉還創(chuàng)造了一批數(shù)學(xué)符號(hào)，如f（x）、Σ、i、e等等，使得數(shù)學(xué)更容易表述、推廣，歐拉是18世紀(jì)數(shù)學(xué)界最杰出的人物之一。并且歐拉把整個(gè)數(shù)學(xué)推至物理的領(lǐng)域，此外還涉及建筑學(xué)、彈道學(xué)、航海學(xué)等領(lǐng)域。

對正整數(shù)x，歐拉函數(shù)是小于x的正整數(shù)中與x互質(zhì)的數(shù)的數(shù)目。求法通式為（圖1）：

x （1 - 1/p1）* … * （1 - 1/pn）。其中p1， p2……pn為x的所有質(zhì)因數(shù)，x是不為0的整數(shù)。φ（1）=1[唯一和1互質(zhì)的數(shù)（小于等于1）就是1本身]。

注意：每種質(zhì)因數(shù)只算一個(gè)。 比如12=2*2*3那么φ（12）=12（1-1/2）（1-1/3）=4。

還可以根據(jù)定義求解，即統(tǒng)計(jì)小于x的所有值中與x互素的個(gè)數(shù)。當(dāng)x為素?cái)?shù)時(shí)，φ（x） = x -1。

其中為歐拉函數(shù)，gcd（a，m）求兩數(shù)最大公約數(shù)，如果為1則互素。

特別是當(dāng)m為素?cái)?shù)時(shí)，該結(jié)論即為費(fèi)馬小定理，因?yàn)橐卜Q歐拉定理是費(fèi)馬小定理的推廣。

基本思路就是根先輸入n和a，并判斷是否互素，然后用定義法和通式法求出歐拉函數(shù)值，計(jì)算冪，求模后判斷，如果為1，則歐拉定理成立。

程序設(shè)計(jì)涉及到的是等級(jí)考試四級(jí)或二級(jí)內(nèi)容。

1.輸入n和a，并判斷是否互素（圖3）

2.求歐拉函數(shù)值（圖4）

3.計(jì)算冪，并求模（圖5）

4.判斷模的值，如果為1，則輸出歐拉定理成立（圖6）

5.完整程序

為了能循環(huán)驗(yàn)證，將所有程序加在循環(huán)里面（圖7）;

如果輸入12和8，則提示非互素，程序返回;輸入12和5，輸出歐拉定理成立;當(dāng)輸入11和5時(shí)，皆為互素，其實(shí)就是費(fèi)馬小定理的驗(yàn)證，這里不做贅述，有興趣的朋友可以參考筆者之前發(fā)的文章（圖8）。

其實(shí)上述這個(gè)程序所涉及的知識(shí)點(diǎn)是等級(jí)考試二級(jí)內(nèi)容。

6.利用自定義函數(shù)

這是等級(jí)考試四級(jí)內(nèi)容。

從上述程序里，大家看到，判斷互素用了兩次，所以使用自定義函數(shù)應(yīng)該是更好一些，思路比較清晰（圖9）。

這里定義了兩個(gè)求最大公約數(shù)的函數(shù)，以此來判斷是否互素，一個(gè)是遞歸函數(shù)，一個(gè)是遞推函數(shù)，放在一起，便于比較理解。fai（）函數(shù)是求歐拉函數(shù)值，ouler（）調(diào)用fai（）函數(shù)求得f值，然后計(jì)算a的f次冪，并對n求模。

主程序中判斷ouler（）函數(shù)返回值，如果為1，則說明歐拉定理成立。

前面我們利用歐拉定理的定義來驗(yàn)證其正確性，而在歐拉函數(shù)求法時(shí)，前面用的是定義形式，這里還可以用通用式來求歐拉函數(shù)值（圖10）。

這是自定義函數(shù)求歐拉函數(shù)值，測試結(jié)果與之前相同。大家也可以研究其他編程方法，這里不再討論。

本文如有不當(dāng)之處，請各位同仁、朋友斧正。