費馬大定理的Python簡單驗證

王德貴 劉洋

在Python的學習過程中，通過編寫程序來解決一些實際問題，也是一種樂趣。在數學史上，關于數論的著名世界難題很多，了解數學家們如何破解這些難題讓人深受啟發和鼓舞。今天我們就用Python來簡單地驗證費馬大定理。

一、費馬大定理簡介

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

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

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

二、創意來源

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

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

三、設計思路

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

四、程序設計

1. 費馬大定理：

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

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

2. 時間復雜度（等級考試四級內容）

在循環的開始和結束，加上計時器，測試發現，指數為3時，在100范圍內耗時大約0.28秒，200范圍內耗時1.94秒，500范圍內耗時36.28秒。而指數為4時，100、200、500范圍內分別耗時0.39秒、1.92秒、60.62秒。隨著數值的增大，需要的時間也更長（圖3）。

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

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

五、測試與改進

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

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

pow（x，y）函數表示的是xy，0

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

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