丢番图集

若有一些整系数多项式$f(n_{1},...,n_{j},x_{1},...,x_{k})$，存在整数$x_{1},...,x_{k}$使得$f(n_{1},...,n_{j},x_{1},...,x_{k})=0$（一个丢番图方程）若且唯若整数多元组$(n_{1},...,n_{j})$属于集$S$，则称$S$为丢番图集。这可以写成

$S=\{\,(n_{1},\dots ,n_{j}):\exists x_{1}\,\dots \,\exists x_{k}\,f(n_{1},\dots ,n_{j},x_{1},\dots ,x_{k})=0\,\}$，其中f是整系数多项式。

因为拉格朗日四平方和定理，可以将上述定义中的“整数”限制为“非负整数”。

例如：因为若$n,x$是正整数， $(n^{2}-xn-x^{2})^{2}-1=0$成立时，$n$必是斐波那契数，因此所有斐波那契数的集是丢番图集。

1970年，马蒂雅谢维奇定理被证明。它说明一个集是丢番图集若且唯若它是递归可枚举集合，解决了希尔伯特第十问题。

有许多集都可以表示为丢番图集，包括质数集[1]（页面存档备份，存于互联网档案馆）。

若有函数$f:\mathbb {Z} ^{j}\to \mathbb {Z}$，使得 $\{(n_{1},...,n_{j},f(n_{1},...,n_{j})\,):\forall n_{i}\in \mathbb {Z} \}$ 为丢番图集，则称$f$为丢番图函数。