使用或不使用 numpy 求解以某个数为模的方程组

Question

假设我有这个方程组：

如果我想用 numpy 解决它，我会简单地这样做：

a = numpy.array([[1, 1, 1],[1,3,9],[1,5,8]])
b = numpy.array([8, 10, 11])

print(numpy.linalg.solve(a,b))

结果将打印此内容：

[7.33333333 0.55555556 0.11111111]

但是，如果方程组是模数 n 怎么办？我已经检查了 numpy 文档，看起来图书馆不支持开箱即用的模方程组。

例如，在模 17 中，该方程组的结果将是 13、10 和 2：

有什么方法可以解决 Python 中的这个方程组？是使用我可能错过的一些 numpy 函数，还是手动编写一些辅助函数？

Answer 1

这可以在 sage, or, if you are adventurous, in glank. There is also a pure python implementation here

中完成

Answer 2

如果gcd(a.det(), m) == 1您可以执行以下操作。这个想法是使用 adj(a) = det(a) * a^(-1) 所以将所有部分保持为整数。

import sympy
from math import gcd

a = sympy.Matrix([[1, 1, 1],[1,3,9],[1,5,8]])
b = sympy.Matrix([8, 10, 11])
m = 17

det = int(a.det())
if gcd(det, m) == 1:
    ans = pow(det, -1, m) * a.adjugate() @ b % m
    print(ans)
else:
    print("don't know")
# Matrix([[13], [10], [2]])

使用或不使用 numpy 求解以某个数为模的方程组

Solving systems of equations modulo a certain number, with or without numpy

python

equation

numpy

linear-algebra

modulo