丟番圖方程

丟番圖方程（英語：Diophantine equation），又稱不定方程，是未知数只能使用整數的整數係數多項式等式；即形式如 $a_{1}x_{1}^{b_{1}}+a_{2}x_{2}^{b_{2}}+......+a_{n}x_{n}^{b_{n}}=c$ 的等式，並且其中所有的 $a_{j}$ 、 $b_{j}$ 和 $c$ 均是整數。若其中能找到一組整數解 $m_{1},m_{2}...m_{n}$ 者則稱之有整數解。

丟番圖問題一般可以有數條等式，其數目比未知數的數目少；丟番圖問題要求找出對所有等式都成立的整數組合。换言之，丟番圖問題定義了代數曲綫或者代數曲面，或更爲一般的幾何形，要求找出其中的柵格點。對丟番圖問題的數學研究稱為丟番圖分析。綫性丟番圖方程爲綫性整數係數多項式等式，即此多項式爲次數爲0或1的單項式的和。

丟番圖方程的名字來源於3世紀希臘數學家丟番圖，他曾對這些方程進行研究，並且是第一個將符號引入代數的數學家。

關於丟番圖方程的理論的形成和發展是二十世紀數學一個很重要的發展。丟番圖方程的例子有貝祖等式、勾股定理的整數解、佩爾方程、四平方和定理和費馬最後定理等。

一次不定方程

一次不定方程是形式如 $a_{1}x_{1}+a_{2}x_{2}+...+a_{n}x_{n}=c$ 的方程，一次不定方程有整數解的充要條件為：

gcd

(a_{1},...,a_{n})|c

換言之 $\gcd(a_{1},...,a_{n})$ 須是 $c$ 的因數，其中 $\gcd(a_{1},...,a_{n})$ 表示 $a_{1},...,a_{n}$ 的最大公因數。

若有二元一次不定方程 $ax+by=c$ ，且 $\gcd(a,b)|c$ ，則其必有一組整數解 $x_{1},y_{1}$ ，並且還有以下關係式：

$x=x_{1}+[b/(a,b)]t$
$y=y_{1}-[a/(a,b)]t$

$t$ 為任意整數，故此一次不定方程有無限多解。請參見貝祖等式。

丟番圖分析

經典問題

方程式有解嗎？
除了一些顯然易見的解外，還有哪些解？
解的數目是有限還是無限？
理論上，所有解是否都能找到？
實際上能否計算出所有解？

希爾伯特第十問題

1900年，希爾伯特提出丟番圖問題的可解答性為他的23個問題中的第10題。1970年，一個數理邏輯的結果馬蒂雅謝維奇定理（英语：Matiyasevich's theorem）說明：一般來說，丟番圖問題都是不可解的。更精確的說法是，不可能存在一個演算法能夠判定任何丟番圖方程是否有解，甚至，在任何相容於皮亚诺算數的系統當中，都能具體構造出一個丟番圖方程，使得沒有任何辦法可以判斷它是否有解。

現代研究

丟番圖集是遞歸可枚舉集。
常用的方法有無窮遞降法和哈賽原理。
丟番圖逼近研究了變數為整數，但係數可為無理數的不等式。

參見

圖靈完全

參考文獻

Mordell, L. J. Diophantine equations. Academic Press. 1969. ISBN 0-12-506250-8.
Schmidt, Wolfgang M. Diophantine approximations and Diophantine equations. Lecture Notes in Mathematics. Springer-Verlag. 2000.
Shorey, T. N.; Tijdeman, R. Exponential Diophantine equations. Cambridge Tracts in Mathematics 87. Cambridge University Press. 1986. ISBN 0-521-26826-5.
Smart, N. P. The algorithmic resolution of Diophantine equations. London Mathematical Society Student Texts 41. Cambridge University Press. 1998. ISBN 0-521-64156-X.
Stillwell, John. Mathematics and its History Second Edition. Springer Science + Business Media Inc. 2004. ISBN 0387953361.