线性丢番图方程求解器

因为这是关于数学的，我从百度百科上百度百科 摘录了一些内容作为开始。

在数学中，线性丢番图方程是一个包含两个或更多未知数的多项式方程，因此只搜索或研究整数解（整数解是所有未知数都取整数值的解）。 线性丢番图方程是两个零阶或一阶单项式和之间的方程。

最简单的线性丢番图方程是这样的:

,

其中a， b 和c是给定的整数, x, y —未知数。

以下定理完整地描述了这些解：当且仅当 c 是 a 和 b 的最大公约数的倍数时，这个丢番图方程有一个解（其中 x 和 y 是整数）。 此外，如果 (x, y) 是一个解，那么其他解的形式为 (x + kv, y - ku)，其中 k 是一个任意整数，而 u 和 v 分别是 a 和 b 除以最大公约得的商。

要找到解，可以使用 扩展欧几里得算法 (除了 a = b = 0 要么有无限多个解，要么没有).

如果a和b是正整数，我们可以使用扩展欧几里得算法找到它们的最大公约数 g，同时使用 и , 所以:

.

如果c是g的倍数，丢翻图方程有解，否则没有解。

如果c是g的倍数，那么:

其中一个可能的解是:

如果a或b有一个是负的，我们可以用它的模来解这个方程，然后相应地改变符号。

如果我们知道其中一个解，我们就能求出它们的一般形式。

令 g = 最大公约数(a,b), 我们得到:

.

把 加到 上，以及把 从 中减去, 我们得到:

任何像这样的数:

,

其中 k 是整数, 都是线性丢番图方程的解。