丟番圖集

维基百科,自由的百科全书
跳转至: 导航搜索

若有一些整係數多項式f(n_1, ..., n_j, x_1, ..., x_k),存在整數x_1,...,x_k使得f(n_1, ..., nj, 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丟番圖函數