丢番图方程

丢番图方程（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.