# Counting solutions to system of linear equations modulo prime

I have implemented Gaussian elimination for solving system of linear equations in the field of modulo prime remainders. If there is a pivot equal to zero I assume the system has no solution but how to calculate number of solutions of such systems when all pivots are non-zero? (i.e. one and more solutions)

The integers modulo a prime form a field, so all assumptions done applying Gaussian eliminations work exactly the same. Luckily, there are no numerical instability problems. The system can be inconsistent (no solutions), underdetermined (several solutions modulo $p$) or have a unique solution modulo $p$.

• I see. Can you please be more specific about finding the number of solutions in case it is underdetermined? Mar 17 '13 at 0:31
• Just as the typical real case, it means that you can express the values of the variables in terms of a subset of them. If this subset has $k$ variables (the rank of the matrix), there will be $p^k$ solutions. Mar 17 '13 at 0:35
• I can't come up with a system where it wouldn't work now but I think that there might be such a system: if you choose a free variable (one of $p$ options) in such way it wouldn't match the rest of system. Mar 20 '13 at 21:32
• According to user anon (math.stackexchange.com/users/11763/anon) from Mathematics chat the proper solution is $p^{dim_{F_{p}} ker A}$. Unfortunately I don't know how to implement that into my code. Mar 20 '13 at 23:07
• @Andrew123321, just get how many of the vectors are linearly independent (by reducing the matrix), that is what they call $\operatorname{dim}_{\mathbb{F}_p} \operatorname{ḱer} A$. Mar 20 '13 at 23:23

It's 2 raised to the power of size of null-space. The reason is that once you have a solution, adding any linear combination of vectors in null-space gives you a valid solution.

This problem comes out when counting number of solutions to "lights out" puzzle, example of solving it in Mathematica using NullSpace operation:

graph = GridGraph[{4, 4}]
n = Length@VertexList@graph;
target = Table[1, {n}];