費馬大定理的Python簡單驗證

王德貴 劉洋

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

一、費馬大定理簡介

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

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

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

二、創(chuàng)意來源

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

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

三、設計思路

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

四、程序設計

1. 費馬大定理：

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

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

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

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

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

如果范圍再增大，則時間復雜度也會增大，需要的時間就會更長。

五、測試與改進

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

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

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

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

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