丟番圖方程

有些問題只有整數解才有意義：你買不了 2.7 隻雞，也無法用三分之一枚硬幣付帳。丟番圖方程就是要求解必須為整數的方程，得名於古希臘數學家丟番圖。同一個方程在實數範圍內或許有無窮多解，作為整數解卻可能只有寥寥幾個，甚至一個也沒有。

最簡單也最重要的情形是關於兩個未知數 x 與 y 的線性丟番圖方程 a x + b y = c。它有整數解，當且僅當 gcd(a, b) 整除 c。當解存在時，可用擴展歐幾里得演算法求出一組解，再讓 x 與 y 以與 b、a 相關的步長朝相反方向滑動，從而生成其餘全部解。

超出線性情形，難度便陡然爆發。像 3、4、5 這樣的勾股數滿足整數方程 x^2 + y^2 = z^2，但費馬的論斷 — 當 n 大於 2 時 x^n + y^n = z^n 沒有正整數解 — 懸而未決長達三百五十多年。一般而言，並不存在一種統一的方法能判定任意丟番圖方程是否有整數解，這一事實本身就是一條著名的定理。