线性丢番图方程组

线性丢番图方程组是线性方程组，其解必须是整数。

这些系统最初可以使用与在线性方程除以实数，用初等的方法比如消去和代换或者更先进的方法从线性代数。一个主要的区别是单线性丢番图方程并不总是有整数解，尽管它总是有实解:例如，线性丢番图方程 $4 x - 2 y = 5$没有整数解(左边是偶数，右边是奇数)，但它有无限多个实数解，形式是 $X = 1.25+t, y = 2t$．

一般的策略是将多个方程简化为一个方程，然后使用wiki上的技术参数化地求解该方程单线性丢番图方程．具体来说，策略如下:

线性丢番图方程组的求解策略

1. 把这个问题变成一个涉及丢番图方程组的问题(如果它是一个应用题)。
2. 就像在一般线性系统中一样:通过代换、加/减多个方程或使用矩阵的这些技术的更正式版本来消除变量。得到一个包含若干变量的线性方程。
3. 用标准数论技术找到该方程的一般参数解。
4. 把这个解代回其他方程来解剩下的变量。
5. 如果问题指定了解的限制条件(例如，大多数情况下，所有的未知数都必须是非负整数)，那么找到满足这些限制条件的解的参数值。

下面的例子演示了这个过程:

下面的例子对于变量可以取的值没有限制，只要求它们必须是整数:

求方程组的所有整数解

$\begin{aligned} 5x+6y+8z &=1 \\ 6x-11y+7z &= 9。结束\{对齐}$

---

解决方案1:
比如说，排除一个变量 $x$．自 $6 x = 11 y-7z + 9$由第二个方程，代入第一个方程 $\开始{对齐}\ frac56 (11 y-7z + 9) + 6 y z + 8 & = 1 \ \ 5 (11 y-7z + 9) + 36 y z + 48 & = 6 \ \ 91 y + 13 z & = -39 \ \ 7 y + z & = 3。结束\{对齐}$所以 $z = 3-7y$，并代回 $x$方程为 $\{对齐}开始6 x & = 11 y-7 (3-7y) + 9 \ \ 6 x & = 60 y + 30 \ \ x和y + 5 = 10,结束\{对齐}$所以解是这样的形式 $(10 y + 5, y, 7 y-3)$,因为 $y$任何整数。 $_ \广场$

解决方案2:
比如说，通过操纵方程来消除一个变量 $y$．第一个方程乘以11，第二个方程乘以6，然后相加得到 $\begin{aligned} 91x+130z &= 65 \\ 7x+10z &= 5。结束\{对齐}$自 $(5,4)$通过检验，这个方程是否有解，解的形式是这样的 $X = -5+10t, z = 4-7t$为 $t$一个整数。 $（$如果数量更多，检查可能会更成问题;生成初始解决方案的另一种方法是考虑例如。 $10 z \ 5枚$国防部 $7$得到 $z \ 4枚$国防部 $7$等。 $）$现在代回第一个方程得到 $\{对齐}开始5 (5 + 10 t) + 6 y + 8 (4-7t) & = 1 \ \ 6 t + 6 y & = 6 \ \ y & = t - 1结束\{对齐}$所以所有的解都是这种形式 $(4-7t 10 t-5, t - 1)$为整数 $t$． $_ \广场$

来自于应用题的方程通常对变量有限制，例如所有的解都必须是正整数。一旦描述了所有的解，这通常会导致一些参数必须满足的不等式。下面是一个简单的例子:

有多少种制作方法 $\ 200美元$从 $1000$硬币，每枚都是25美分、10美分或5美分?

---

让 $问d n$分别是25美分，10美分和5美分的数目。然后

$\begin{aligned} 25q+10d+5n &=20000 \\ q+d+n &=1000。结束\{对齐}$

写作 $q = 1000 - d - n$代入第一个方程得到 $25000 - 15 - 20 d - n = 20000$，则简化为

$3 d + 4 n = 1000。$

自 $(0250)$一个解，所有的解都是由 $250 - 3 - (4 t, t)$对于一些整数 $t$．在这种情况下 $q = 750 - t$，所以通解是 $(750 - t, 4 t, 250 - 3 - t)$．

因为所有的数都是非负的，我们分别有， $t \勒750$， $t \通用电气0$, $3 t \ 250$．最后的不平等减少为 $t \ 83 \ frac13勒$的可接受值 $t$是 $0 1 \ ldots, 83年$．这就得到了 $\ fbox {84}$解决方案。 $_ \广场$