是否有任何算法可以求解以不同模空间表示的方程组？例如，考虑这个方程组：
(x1 + x2 ) % 2 = 0
( x2 + x3) % 2 = 0
(x1 + x2 + x3) % 3 = 2
该系统的解决方案之一是：
x1 = 0
x2 = 2
x3 = 0
我怎么能算术找到这个解决方案（不使用蛮力算法）？
谢谢
问问题
1309 次
3 回答
3
您可以将这些方程式重写为
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)，您应该会得到一个解决方案。
于 2017-02-05T08:18:18.573 回答
0
您可以将系统转换为模 LCM（最小公倍数）。只需找到所有方程模的 LCM，并适当地乘以每个方程。
于 2017-02-05T08:27:42.320 回答
0
第一行与说 x1 相同，x2 都是偶数或所有奇数。第二行与说x2相同，x3全是偶数或全是奇数。因此 x1,x2,x3 都是偶数或奇数。从第三行开始，我们可以将问题替换为“累积到 3k+2 的 3 个奇数或 3 个偶数”。
于 2017-02-05T08:09:30.070 回答