丢番图集

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

${\displaystyle 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是整系数多项式。

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

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

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

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

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