Using Numpy to solve Linear Equations involving modulo operation

Question

I know that numpy can be used to solve linear equations as shown below:

import numpy as np

# Solving following system of linear equation
# 1a + 1b = 35
# 2a + 4b = 94

a = np.array([[1, 1],[2,4]])
b = np.array([35, 94])

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

Now, let's say, I have linear equations which involve the modulo operation. Can numpy solve such equations as well?

Equations of the following form:

m = 2 ** 31 - 1

(207560540 ∗ a + b) modulo m = 956631177
(956631177 ∗ a + b) modulo m = 2037688522

Thanks.

Answer 1

This is modular arithmetic, but unfortunately numpy doesn't support this.

But you can solve it "manually" in python.

Since m is prime, first define the inverse modulo m (from here):

def inv(x): return pow(x,m-2,m) # inverse mod m, because x**(m-1) %m = 1 (Fermat).

Then, with the system posed as :

A1=207560540
C1=956631177
#(A1 ∗ a + b) modulo m = C1  : equation (1)

A2=956631177 
C2=2037688522
#(A2 ∗ a + b) modulo m = C2   : equation (2)

You have :

A = A2-A1  #(2)-(1)
C = C2-C1
#A*a = C  % m
X=inv(A)  
a=(C*X)%m

And :

D = A2*C1-A1*C2  # A2*(1) - A1*(2) 
#A*b = D %m
b=(D*X)%m

Check-up:

print(a,b) 
print((A1*a+b)%m,C1)
print((A2*a+b)%m,C2)

16807 78125  # a and b
956631177 956631177
2037688522 2037688522

Answer 2

You could try to rewrite this into a normal linear system. Something like this:

(207560540 ∗ a + b) + c*m + d*0 = 956631177
(956631177 ∗ a + b) + c*0 + d m = 2037688522

If you now solve this linear system you should get your answer.