# Solving Linear Equations over finite field $Z_q$

Suppose we are given a linear equation $$Ax=b$$, where $$A \in Z_q^{n \times m}$$ and $$b \in Z_q^n$$.

Note that $$q$$ is a prime here, and $$Rank(A)= Rank(A;b)=n.

I wonder whether the following ROUCHÉ–CAPELLI THEOREM still holds in the finite field $$Z_q$$:

Given a system of linear equations, $$Ax = b$$, it holds that:

1. $$Rank(A) = Rank(A; b)$$ ⇔ the system is unsolvable.
2. $$Rank(A) = Rank(A; b)$$ ⇔ the system is solvable.
3. $$Rank(A) = Rank(A; b) = m$$ ⇔ the system has unique solution.
4. $$Rank(A) = Rank(A; b) < m$$ ⇔ the system has infinite solutions.

Is there any standard theorem in the thesis or textbook if it does? I need to cite the standard theorem into my thesis, but I can't find any.

Thanks.

• How could you have an infinite number of solution when you only have a finite number of vectors of dimension $m$? Anyway, by the very definition of the rank (on any vector space, thus on vector space over $Z_q$ too), Rank(A)=Rank(A;b) exactly says that $b$ is linearly dependent on the column of $A$. Now, if you have a solution $x_0$, your set of solution is in one to one correspondence with $x_0+Ker(A)$, so you can deduce the number of solution from there.
– holf
Oct 31, 2022 at 15:05
• This looks like a question about pure math, with no computer science knowledge needed to answer it. As such it does not seem on-topic here.
– D.W.
Oct 31, 2022 at 21:34