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

王德貴 劉洋

在Python的學(xué)習(xí)過程中，通過編寫程序來解決一些實(shí)際問題，也是一種樂趣。在數(shù)學(xué)史上，關(guān)于數(shù)論的著名世界難題很多，了解數(shù)學(xué)家們?nèi)绾纹平膺@些難題讓人深受啟發(fā)和鼓舞。今天我們就用Python來簡(jiǎn)單地驗(yàn)證費(fèi)馬大定理。

一、費(fèi)馬大定理簡(jiǎn)介

費(fèi)馬大定理，又稱費(fèi)馬問題，是數(shù)論中最著名的世界難題之一。

概括來說就是當(dāng)整數(shù)n>2時(shí)，關(guān)于x，y，z的方程xn+yn=zn，無正整數(shù)解。

你看這個(gè)方程是不是和求勾股數(shù)的類似，只是2次方變成了n次方，我們后面的驗(yàn)證，也是根據(jù)這個(gè)思路進(jìn)行的。

二、創(chuàng)意來源

看到這個(gè)定理內(nèi)容，就想到了勾股數(shù)，我們用Python編寫程序，在一定取值范圍內(nèi)驗(yàn)證費(fèi)馬大定理。

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

三、設(shè)計(jì)思路

根據(jù)《趣味數(shù)學(xué)——勾股數(shù)》一文的分析，勾股數(shù)是平方，這里就變成了大于2的正整數(shù)，程序設(shè)計(jì)不難，驗(yàn)證的范圍越大，冪次越高，時(shí)間復(fù)雜度會(huì)幾何級(jí)數(shù)增大，大家可以自行測(cè)試。

四、程序設(shè)計(jì)

1. 費(fèi)馬大定理：

根據(jù)勾股數(shù)的例子，我們不難寫出Python程序。代碼如圖1。

程序中有三重for循環(huán)，外層循環(huán)，即是輸入的最大范圍，然后再確定指數(shù)冪，在1～n整數(shù)范圍內(nèi)逐個(gè)驗(yàn)證，如果有滿足條件的x，y，標(biāo)記s=1，然后輸出屏幕，否則繼續(xù)驗(yàn)證，如果s=0的值沒有改變，即沒找到任何滿足條件的數(shù)，則輸出無整數(shù)解（圖2）。

2. 時(shí)間復(fù)雜度（等級(jí)考試四級(jí)內(nèi)容）

在循環(huán)的開始和結(jié)束，加上計(jì)時(shí)器，測(cè)試發(fā)現(xiàn)，指數(shù)為3時(shí)，在100范圍內(nèi)耗時(shí)大約0.28秒，200范圍內(nèi)耗時(shí)1.94秒，500范圍內(nèi)耗時(shí)36.28秒。而指數(shù)為4時(shí)，100、200、500范圍內(nèi)分別耗時(shí)0.39秒、1.92秒、60.62秒。隨著數(shù)值的增大，需要的時(shí)間也更長(zhǎng)（圖3）。

時(shí)間復(fù)雜度就要根據(jù)你輸入的范圍決定了。比如100，那時(shí)間復(fù)雜度即為100萬。

如果范圍再增大，則時(shí)間復(fù)雜度也會(huì)增大，需要的時(shí)間就會(huì)更長(zhǎng)。

五、測(cè)試與改進(jìn)

通過測(cè)試，在一定范圍內(nèi)，均得到了驗(yàn)證，但數(shù)值過大時(shí)，用時(shí)較長(zhǎng)。當(dāng)然我們要證明一個(gè)定理，不可能把所有值都驗(yàn)證，還需要理論上的證明。

因此費(fèi)馬大定理程序，可以利用pow（）函數(shù)進(jìn)行改進(jìn)，減小時(shí)間復(fù)雜度（圖4）。

pow（x，y）函數(shù)表示的是xy，0

歷經(jīng)多年，經(jīng)過多位數(shù)學(xué)家的研究和證明，費(fèi)馬大定理得到了一步步的成果?！吨袊?guó)數(shù)學(xué)會(huì)通訊》1987年第2期據(jù)國(guó)外消息報(bào)道，費(fèi)馬猜想近年來取得了驚人的研究成果：格朗維爾和希思·布龍證明了「對(duì)幾乎所有的指數(shù)，費(fèi)馬大定理成立」。即若命N（x）表示在不超過x的整數(shù)中使費(fèi)馬猜想不成立的指數(shù)個(gè)數(shù)，則證明中用到了法爾廷斯（Faltings）的結(jié)果。另外一個(gè)重要結(jié)果是：費(fèi)馬猜想若有反例，即存在x>0，y>0，z>0，n>2，使xn+yn=zn，則x>101800000。直到1994年10月英國(guó)數(shù)學(xué)家安德魯·懷爾斯（Andrew Wiles）終于證明了費(fèi)馬大定理，為這個(gè)從1637年至今的數(shù)學(xué)謎題畫上了圓滿的句號(hào)。

我們這里只是做個(gè)簡(jiǎn)單的、基本的驗(yàn)證，希望大家能發(fā)揮自己的智慧和力量，進(jìn)一步研究和探討，找到一個(gè)更好的算法，來證明費(fèi)馬大定理！