使用不同模数解决一组联立方程

Question

是否有算法可以解决在不同模空间中表示的方程组？例如，考虑以下方程组：

(x1 + x2     ) % 2 = 0
(     x2 + x3) % 2 = 0
(x1 + x2 + x3) % 3 = 2

这个系统的解决方案之一是：

x1 = 0
x2 = 2
x3 = 0

我该如何算出这个解（不使用蛮力算法）？

谢谢。

- Thomas Bernard

---

有趣的问题。当然，Presburger算术的决策过程是可行的，但它很复杂且缓慢。有趣的情况是当模数是相同质数的幂时；给定一个方程... = ... mod (p q)，其中gcd(p, q) = 1，我们可以将其拆分为... = ... mod p和... = ... mod q，然后使用中国剩余定理组装最终解决方案。 - David Eisenstat

Answer 1

您可以将这些方程式重写为：

x1 + x2 = 2*n1
x2 + x3 = 2*n2
x1 + x2 + x3 = 3*n3 + 2

现在，这是一个关于线性不定方程的问题，在文献中有解决方案。

例如：http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation 另请参见：https://www.math.uwaterloo.ca/~wgilbert/Research/GilbertPathria.pdf 算法：

将xi写成nks的函数。

在这种情况下：

x3 = 3*n3 + 2 - 2*n1
x2 = 2*n2 - (3*n3 + 2 - 2*n1)
x1 = 2*n1 - (2*n2 - (3*n3 + 2 - 2*n1))

由于右侧没有除法，因此选择任意的(n1, n2, n3)即可得到解决方案。

- ElKamina

---

有没有一种算法可以自动解决像这样的丢番图方程组，我没有找到任何方法... - Thomas Bernard

感谢您的回答。使用矩阵单模约化方法，我能够自动将xi表示为nis的函数。但现在我基本上得到了一个具有m个未知ni变量的系统（而不是m个xi未知变量），我并不真正理解我的算法如何自动选择正确的ni值（在这个例子中没有除法，因此每个ni都是自由的。但这总是情况吗？我不能以ni为约束吗？） - Thomas Bernard

@ThomasBernard 我在这个领域不是专家。你应该阅读我提供的论文链接。无论如何，一般情况并不简单。 - ElKamina

是的，我读了这篇论文。事实上，一般情况远非琐碎：https://arxiv.org/pdf/1206.5114v1.pdf。至于我的用例，在存在多个解的情况下，我还必须找到使Sum{abs(xi)}最小的解，该论文的方法不适合我的需求。最终，我采用了矩阵缩减和暴力解空间搜索的混合解决方案，这让我很满意（在我的桌面上使用数百个变量运行时间不到一秒）。感谢您的帮助。 - Thomas Bernard

Answer 2

第一行相当于说x1，x2都是偶数或奇数。 第二行相当于说x2，x3都是偶数或奇数。 因此，x1、x2、x3都是偶数或奇数。 从第三行开始，我们可以将问题替换为“累加到3k+2的3个奇数或偶数”。

- Zeta

Answer 3

你可以将系统转换为模L最小公倍数。只需找到所有方程的模LCM，并适当地乘以每个方程。

- valdo

---

谢谢你的回答。你能再详细解释一下吗？当你说“适当地乘以每个方程”时，具体是什么意思？在我发布的示例中，LCM是6，那么转换为模6的系统会是什么样子？ - Thomas Bernard

@ThomasBernard 是的，没错。前两个应该乘以3，最后一个应该乘以2。 - valdo

谢谢。然而我现在遇到了另一个问题。为了解决我的线性方程组模n的问题，我过去常常使用高斯-约当消元算法，需要将某些行乘以它们的倒数模n，以便在行梯矩阵的对角线上只得到"1"值。然而，在这里是不可能的，因为2^-1 mod 6和3^-1 mod 6都不存在...（而且我的矩阵中只有2、3和0值） - Thomas Bernard