Solving Systems Of Equations Modulo A Certain Number, With Or Without Numpy

Suppose I have this system of equations: If I wanted to solve it using numpy, I would simply do this: a = numpy.array([[1, 1, 1],[1,3,9],[1,5,8]]) b = numpy.array([8, 10, 11]) pr

Solution 1:

If gcd(a.det(), m) == 1 you can do following. The idea is to use adj(a) = det(a) * a^(-1) so keeping all parts as integer.

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]])

Solution 2:

This can be done in sage, or, if you are adventurous, in glank. There is also a pure python implementation here