内容

• 脚步
• 第 1 部分（共 4 部分）：如何编写方程式
• 第 2 部分（共 4 部分）：如何编写欧几里德算法
• 第 3 部分（共 4 部分）：如何使用 Euclid 算法找到解决方案
• 第 4 部分（共 4 部分）：寻找无限的其他解决方案

要求解线性丢番图方程，您需要找到变量“x”和“y”的值，它们是整数。整数解决方案比平常更复杂，需要一组特定的操作。首先，您需要计算系数的最大公约数 (GCD)，然后找到解决方案。一旦找到线性方程的一个整数解，就可以使用一种简单的模式来找到无数其他解。

脚步

第 1 部分（共 4 部分）：如何编写方程式

1. 1 以标准形式写出方程。 线性方程是其中变量的指数不超过 1 的方程。要求解这样的线性方程，首先将其写成标准形式。线性方程的标准形式如下所示： ${ displaystyle Ax + By = C}$， 在哪里 ${ 显示样式 A, B}$ 和 ${ 显示样式 C}$ - 整数。
   • 如果方程以不同形式给出，请使用基本代数运算将其转化为标准形式。例如，给定方程 ${ 显示样式 23x + 4y-7x = -3y + 15}$...给出相似的项并写出这样的等式： ${ 显示样式 16x + 7y = 15}$.
2. 2 简化方程（如果可能）。 当你以标准形式写出方程时，看看系数 ${ 显示样式 A, B}$ 和 ${ 显示样式 C}$...如果这些赔率有 GCD，则将所有三个赔率除以它。这种简化方程的解也将是原方程的解。
   • 例如，如果所有三个系数都是偶数，则将它们至少除以 2。例如：
     • ${ 显示样式 42x + 36y = 48}$ （所有成员都可以被 2 整除）
     • ${ 显示样式 21x + 18y = 24}$ （现在所有成员都可以被 3 整除）
     • ${ 显示样式 7x + 6y = 8}$ （这个等式不能再简化了）
3. 3 检查方程是否可以求解。 在某些情况下，您可以立即声明方程没有解。如果系数“C”不能被系数“A”和“B”的 GCD 整除，则方程无解。
   • 例如，如果两个系数 ${ 显示样式 A}$ 和 ${ 显示样式 B}$ 是偶数，那么系数 ${ 显示样式 C}$ 必须是均匀的。但是如果 ${ 显示样式 C}$ 奇怪，那就没有办法了。
     • 等式 ${ 显示样式 2x + 4y = 21}$ 没有整数解。
     • 等式 ${ 显示样式 5x + 10y = 17}$ 没有整数解，因为方程的左边可以被 5 整除而右边不能。

第 2 部分（共 4 部分）：如何编写欧几里德算法

1. 1 了解欧几里得算法。 它是一系列重复的除法，其中前一个余数用作下一个除数。将数字整除的最后一个除数是两个数字的最大公约数 (GCD)。
   • 例如，让我们使用欧几里得算法找到数字 272 和 36 的 GCD：
     • ${ 显示样式 272 = 7 * 36 + 20}$ - 将较大的数 (272) 除以较小的数 (36) 并注意余数 (20)；
     • ${ 显示样式 36 = 1 * 20 + 16}$ - 将前一个除数 (36) 除以前一个余数 (20)。注意新的残基（16）；
     • ${ 显示样式 20 = 1 * 16 + 4}$ - 将前一个除数 (20) 除以前一个余数 (16)。注意新的残基（4）；
     • ${ 显示样式 16 = 4 * 4 + 0}$ - 将前一个除数 (16) 除以前一个余数 (4)。由于余数为 0，我们可以说 4 是原始两个数 272 和 36 的 GCD。
2. 2 将欧几里得算法应用于系数“A”和“B”。 当您以标准形式编写线性方程时，确定系数“A”和“B”，然后将欧几里得算法应用于它们以找到 GCD。例如，给定一个线性方程 ${ 显示样式 87x-64y = 3}$.
   • 这是系数 A = 87 和 B = 64 的欧几里德算法：
     • ${ 显示样式 87 = 1 * 64 + 23}$
     • ${ 显示样式 64 = 2 * 23 + 18}$
     • ${ 显示样式 23 = 1 * 18 + 5}$
     • ${ 显示样式 18 = 3 * 5 + 3}$
     • ${ 显示样式 5 = 1 * 3 + 2}$
     • ${ 显示样式 3 = 1 * 2 + 1}$
     • ${ 显示样式 2 = 2 * 1 + 0}$
3. 3 找出最大公因数 (GCD)。 由于最后一个除数是 1，因此 GCD 87 和 64 是 1。因此，87 和 64 是彼此相关的素数。
4. 4 分析结果。 当你找到 gcd 系数时 ${ 显示样式 A}$ 和 ${ 显示样式 B}$, 与系数比较 ${ 显示样式 C}$ 原方程。如果 ${ 显示样式 C}$ 可被 gcd 整除 ${ 显示样式 A}$ 和 ${ 显示样式 B}$，方程有整数解；否则方程无解。
   • 例如，方程 ${ 显示样式 87x-64y = 3}$ 可以求解，因为 3 可以被 1 整除（gcd = 1）。
   • 例如，假设 GCD = 5。 3 不能被 5 整除，所以这个方程没有整数解。
   • 如下所示，如果一个方程有一个整数解，那么它也有无穷多个其他整数解。

第 3 部分（共 4 部分）：如何使用 Euclid 算法找到解决方案

1. 1 对计算 GCD 的步骤进行编号。 要找到线性方程的解，您需要使用欧几里得算法作为代入和化简过程的基础。
   • 首先对计算 GCD 的步骤进行编号。计算过程如下所示：
     • ${ displaystyle { text {Step 1}}: 87 = (1 * 64) +23}$
     • ${ displaystyle { text {Step 2}}: 64 = (2 * 23) +18}$
     • ${ displaystyle { text {Step 3}}: 23 = (1 * 18) +5}$
     • ${ displaystyle { text {Step 4}}: 18 = (3 * 5) +3}$
     • ${ displaystyle { text {Step 5}}: 5 = (1 * 3) +2}$
     • ${ displaystyle { text {Step 6}}: 3 = (1 * 2) +1}$
     • ${ displaystyle { text {Step 7}}: 2 = (2 * 1) +0}$
2. 2 注意最后一步，这里还有余数。 重写此步骤的等式以隔离余数。
   • 在我们的示例中，带有余数的最后一步是第 6 步。余数为 1。将第 6 步中的方程改写如下：
     • ${ displaystyle 1 = 3- (1 * 2)}$
3. 3 隔离上一步的其余部分。 这个过程是一个循序渐进的“向上”。每次您都将在上一步中隔离等式中的余数。
   • 隔离步骤 5 中方程的其余部分：
     • ${ displaystyle 2 = 5- (1 * 3)}$ 要么 ${ 显示样式 2 = 5-3}$
4. 4 替换和简化。 请注意，步骤 6 中的方程包含数字 2，而步骤 5 中的方程中，数字 2 是孤立的。因此，将步骤 6 中的公式中的“2”替换为步骤 5 中的表达式：
   • ${ 显示样式 1 = 3-2}$ （步骤 6 的等式）
   • ${ 显示样式 1 = 3- (5-3)}$ （代替 2，一个表达式被替换）
   • ${ 显示样式 1 = 3-5 + 3}$ （左括号）
   • ${ 显示样式 1 = 2 (3) -5}$ （简化）
5. 5 重复替换和简化过程。 重复上述过程，以相反的顺序遍历欧几里得算法。每次您将重写上一步中的方程式并将其插入您得到的最后一个方程式中。
   • 我们查看的最后一步是第 5 步。因此请转到第 4 步并隔离该步骤的等式中的余数：
     • ${ displaystyle 3 = 18- (3 * 5)}$
   • 将此表达式替换为最后一个等式中的“3”：
     • ${ displaystyle 1 = 2 (18-3 * 5) -5}$
     • ${ 显示样式 1 = 2 (18) -6 (5) -5}$
     • ${ 显示样式 1 = 2 (18) -7 (5)}$
6. 6 继续替换和简化过程。 此过程将重复进行，直到您到达欧几里得算法的初始步骤。该过程的目标是用要求解的原始方程的系数 87 和 64 编写方程。在我们的例子中：
   • ${ 显示样式 1 = 2 (18) -7 (5)}$
   • ${ displaystyle 1 = 2 (18) -7 (23-18)}$ （替换步骤 3 中的表达式）
     • ${ displaystyle 1 = 2 (18) -7 (23) +7 (18)}$
     • ${ 显示样式 1 = 9 (18) -7 (23)}$
   • ${ displaystyle 1 = 9 (64-2 * 23) -7 (23)}$ （替换步骤 2 中的表达式）
     • ${ displaystyle 1 = 9 (64) -18 (23) -7 (23)}$
     • ${ 显示样式 1 = 9 (64) -25 (23)}$
   • ${ displaystyle 1 = 9 (64) -25 (87-64)}$ （替换步骤 1 中的表达式）
     • ${ displaystyle 1 = 9 (64) -25 (87) +25 (64)}$
     • ${ 显示样式 1 = 34 (64) -25 (87)}$
7. 7 根据原始系数重写结果方程。 当您返回到欧几里得算法的第一步时，您将看到结果方程包含原始方程的两个系数。重写方程，使其项的顺序与原始方程的系数相匹配。
   • 在我们的例子中，原始方程 ${ 显示样式 87x-64y = 3}$...因此，重写结果方程，使系数一致。特别注意系数“64”。在原方程中，这个系数是负的，在欧几里得算法中，它是正的。因此，因子 34 必须为负数。最后的等式会写成这样：
     • ${ 显示样式 87 (-25) -64 (-34) = 1}$
8. 8 应用适当的乘数以找到解决方案。 请注意，在我们的示例中，GCD = 1，因此最终方程为 1。但原始方程 (87x-64y) 为 3。因此，最终方程中的所有项必须乘以 3 才能得到解：
   • ${ displaystyle 87 (-25 * 3) -64 (-34 * 3) = 1 * 3}$
   • ${ 显示样式 87 (-75) -64 (-102) = 3}$
9. 9 写出方程的整数解。 与原始方程系数相乘的数字就是该方程的解。
   • 在我们的示例中，将解写为一对坐标： ${ displaystyle (x, y) = (- 75, -102)}$.

第 4 部分（共 4 部分）：寻找无限的其他解决方案

1. 1 了解有无数种解决方案。 如果一个线性方程有一个整数解，那么它必定有无穷多个整数解。这是一个快速证明（以代数形式）：
   • ${ displaystyle Ax + By = C}$
   • ${ displaystyle A (x + B) + B (y-A) = C}$ （如果将“B”加到“x”上并从“y”中减去“A”，则原方程的值不会改变）
2. 2 记录原始 x 和 y 值。 计算下一个（无限）解的模板从您已经找到的唯一解开始。
   • 在我们的例子中，解决方案是一对坐标 ${ displaystyle (x, y) = (- 75, -102)}$.
3. 3 将“B”因子添加到“x”值。 这样做可以找到新的 x 值。
   • 在我们的示例中，x = -75，B = -64：
     • ${ displaystyle x = -75 + (- 64) = - 139}$
   • 因此，新值“x”：x = -139。
4. 4 从“y”值中减去“A”因子。 为了不改变原方程的值，当给“x”加一个数时，需要从“y”中减去另一个数。
   • 在我们的示例中，y = -102，A = 87：
     • ${ displaystyle y = -102-87 = -189}$
   • 因此，“y”的新值：y = -189。
   • 新的坐标对将这样写： ${ displaystyle (x, y) = (- 139, -189)}$.
5. 5 检查解决方案。 要验证新坐标对是原始方程的解，请将值代入方程。
   • ${ 显示样式 87x-64y = 3}$
   • ${ 显示样式 87 (-139) -64 (-189) = 3}$
   • ${ 显示样式 3 = 3}$
   • 既然满足了等式，那么这个决定是正确的。
6. 6 写下表达式以找到许多解决方案。 “x”值将等于原始解加上“B”因子的任意倍数。这可以写成以下表达式：
   • x (k) = x + k (B)，其中“x (k)”是“x”值的集合，“x”是您找到的“x”的原始（第一个）值。
     • 在我们的例子中：
     • ${ displaystyle x (k) = - 75-64k}$
   • y (k) = y-k (A)，其中 y (k) 是 y 值的集合，y 是您找到的原始（第一个）y 值。
     • 在我们的例子中：
     • ${ displaystyle y (k) = - 102-87k}$