丢番图方程

丢番图方程是只允许整数解的方程。

希尔伯特第十问题询问是否存在一种算法来确定任意丢番图方程是否有解。对于一阶丢番图方程的解，这样的算法确实存在。然而，尤里·马季亚谢维奇在 1970 年证明了获得通解是不可能的 (Matiyasevich 1970, Davis 1973, Davis and Hersh 1973, Davis 1982, Matiyasevich 1993)，他通过证明关系式 (其中 是第 个 斐波那契数) 是丢番图式的。更具体地说，马季亚谢维奇证明存在一个关于 ，、 和一些其他变量 、、、... 的多项式 P，其性质是 当且仅当 存在整数 、、、... 使得 。

马季亚谢维奇的结果填补了马丁·戴维斯、希拉里·普特南和朱莉娅·罗宾逊先前工作中的一个关键空白。马季亚谢维奇和罗宾逊随后的工作证明，即使对于包含十三个变量的方程，也不可能存在确定是否存在解的算法。马季亚谢维奇随后将此结果改进为仅包含九个变量的方程 (Jones and Matiyasevich 1982)。

奥格威和安德森 (1988) 给出了一些具有已知和未知解的丢番图方程。

线性丢番图方程（在两个变量中）是以下一般形式的方程

(1)

其中解是在 、 和 为整数的情况下寻求的。这类方程可以完全求解，第一个已知的解是由婆罗摩笈多构造的。考虑方程

(2)

现在使用欧几里得算法的变体，令 且

			(3)
			(4)
			(5)
			(6)

从底部开始得到

			(7)
			(8)

因此

			(9)
			(10)

将此过程一直继续回到顶部。

以方程为例

(11)

并应用上述算法得到

(12)

因此解为 ，。

上述过程可以简化，注意到最左边的两列偏移一个条目并且符号交替，因为它们必须如此，因为

			(13)
			(14)
			(15)

因此 和 的系数相同，并且

(16)

因此，使用此信息重复上述示例得到

(17)

并且我们恢复了上述解。

称以下方程的解为

(18)

和 。如果 或 前面的符号为负，则解上述方程并从下表获取解的符号

方程

事实上，方程的解

(19)

等价于找到 的连分数，其中 和 互质 (Olds 1963)。如果分数中有 项，则取第 个收敛项 。但是

(20)

因此一个解是 ，，通解为

			(21)
			(22)

其中 是任意整数。用最小正整数表示的解是通过选择适当的 给出的。

现在考虑以下形式的一般一阶方程

(23)

最大公约数 可以除以得到

(24)

其中 ，，且 。如果 ，则 不是整数，并且该方程不可能有整数解。因此，一般一阶方程有整数解的充要条件是 。如果是这种情况，则解

(25)

并将解乘以 ，因为

(26)

D. 威尔逊编制了一个正整数的最小第 次幂的列表，这些正整数是不同较小正整数的第 次幂之和。前几个是 3、5、6、15、12、25、40，...(OEIS A030052)

			(27)
			(28)
			(29)
			(30)
			(31)
			(32)
			(33)
			(34)
			(35)
			(36)