# 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$.
• 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. – vonbrand 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. – A123321 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. – A123321 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$. – vonbrand Mar 20 '13 at 23:23