A system of linear equations $Ax=b$ over a (finite) field has no solutions if and only if there is a linear combination of the equations which gives $0 = k$ for some $k \not \equiv 0$. Thus, this linear combination can be thought of as a "certificate" that $Ax =b$ has no solutions over that field. My questions are:
- For a system of linear equations mod $q$ where $q$ is not a prime or a prime power, is it still the case that if $Ax =b \bmod q$ has no solutions then there is a linear combination (mod $q$) of the equations of $Ax =b \bmod q$ that gives $0=k$, for $k\not \equiv 0$?
Said differently, a linear system of congruences which has no solution always has a linear combination of those congruences which is equivalent to $0 =k \bmod q$ for $k \not \equiv 0$
- If not, is there some sort of analogous certificate of having no solutions for mod $q$, where $q$ is not a prime or a power of a prime?
Thank you very much for the help
OK, so let $A$ be a $m\times n$ matrix with coefficients in $\mathbb{Z}/q\mathbb{Z}$.
Take any $m\times n$ matrix $M$ with coefficients in $\mathbb{Z}$ such that $A=M \mod q$.
Reducing to a Smith normal form gives you an equality $UMV=R$, where $U\in GL_m(\mathbb{Z})$ and $V\in GL_n(\mathbb{Z})$ and $R$ is a $m\times n$ matrix with coefficients in $\mathbb{Z}$, and which has the form $\pmatrix{D & 0 \cr 0 & 0}$, where $D=\pmatrix{d_1 & & \cr & \ddots & d_r}$, where $d_1\mid \cdots \mid d_r$ (and $d_i>0$).
$R$ is called the Smith normal form of $M$ and you can find $U,R,V$ explicitely (you have lot of explanations on the web).
In particular, note that $U,V$ both have determinant $\pm 1$, so they are still invertible when reducing mod $q$.
All in all, your linear system is $URVx=b \mod q$, that is $Ru=U^{-1} b \mod q$, where $y=Vx$. Since $V$ is invertible mod $q$, your linear system will have a solution mod q if and only if the linear system $Ry=V^{-1} b$ has a solution. Now it boils down to a system of the form $d_iy_i =c_i \mod q$, where $c_i$ is the ith coordinate of $V^{-1 }b$.
Conclusion: you are reduced to study an equation of the form $dy=c \mod q$.
We may possibly have $d=0$ (because some of the $d_i's$ may be divisible by $q$, or you could have $r<n$ , or both), but what follows is valid in any situation.
Set $g=gcd (q,d)$.
I claim that this has a solution if and only if $g\mid c$. Indeed $c=dy-kq$ for some $k$, which is a multiple of $g$, so the condition is necessary.
Conversely if $g\mid c$, write $c=gc'$, $d=gd'$ and $q=g q'$. Then your equation is equivalent to $d'y=c' \mod q'$, which has a solution because $d'$ and $q'$ are croprime, so $d'$ is invertible mod $q'$.
Final remark: you probably do not need the Smith normal form. You have slightly different standard forms which are computable using only row operations, but the final result is neat enough and you do not have to think about anything once you are reduced to a "diagonal" system.