Linear Solve with Modular Arithmetic

I am interested in using LinearSolve[m,b] which will find a solution to the equation $m.x=b$, where I am in mod 2 arithmetic. Is there any way to perform this computation in Mathematica ?

• You know that LinearSolve[] takes a Modulus option, no? – J. M. will be back soon Oct 4 '12 at 22:14
• @J.M., I did not know that. Can you tell me how I would do this syntactically? – Samuel Reid Oct 4 '12 at 22:17
• Did you look at the docs for LinearSolve[]? – J. M. will be back soon Oct 4 '12 at 22:19
• @Artes Sorry that I forgot to accept your answer, yes it was helpful and exactly what I needed to finish writing my Algorithm. Thanks! – Samuel Reid Feb 5 '13 at 23:40

There is an option Modulus in certain algebraic functions (Solve, LinearSolve, Det,Factor etc.) to specify that integers are to be treated modulo an integer n. Consider e.g.

m0 = {{4, 6, 6}, {6, 3, 2}, {1, 4, 4}};
b0 = {4, 2, 1};

then

LinearSolve[ m0, b0, Modulus -> 2]
{1, 0, 0}

You can work with LinearSolve specifying only the first variable, then it generates a linear operator, e.g. let :

m1 = {{1, 0, 1, 5}, {0, 4, 6, 7}, {0, 2, 3, 1}, {1, 7, 0, 8}};
c1 = LinearSolve[m1, Modulus -> 2]
LinearSolveFunction[{4,4},<>]

c1 yields automatically solutions modulo 2. It can be convenient to work with Manipulate :

Manipulate[  c1[{a1, a2, a3, a4}],
{a1, -5, 5, 1}, {a2, -5, 5, 1}, {a3, -5, 5, 1}, {a4, -5, 5, 1}] 