# List the primes for which the following system of linear equations DOES NOT have a solution in $\mathbb{Z}_p$

Let $p$ be a prime and consider the field $\Bbb Z_p$. List the primes for which the following system of linear equations does not have a solution in $\Bbb Z_p$:

\begin{align} 5x + 3y &= 4 \tag{1}\\ 3x + 6y & = 1\tag{2} \end{align}

My try is as follows:

Determinant of the coefficient matrix is $21$. $21$ will be 0 if $p=3$ or $7$. So the answer will be $3$ and $7$. is it correct?

-
It's a start. 3 and 7 are the only possibilities, but determinant zero doesn't guarantee there are no solutions, it just makes it possible that there are no solutions. You have to now look at those two cases, and see whether solutions exist. –  Gerry Myerson Sep 17 '12 at 12:36

Form the extended coefficients matrix and apply Gauss Reduction as much as possible.

To begin with, if $\,p=5\,$ then the first equation is $\,3y=4\Longrightarrow y=4\cdot 3^{-1}=4\cdot 2=3\,$ , and substituing in eq. 2 we get $\,3x+3=1\Longrightarrow 3x=-2=3\Longrightarrow x=1\,$ , so there's a unique solution: $\,(1,3)\,$

If $\,p\neq5\,$ we get

$$\begin{pmatrix}5&3&4\\3&6&1\end{pmatrix}\stackrel{R_1/5}\longrightarrow \begin{pmatrix}1&3/5&4/5\\3&6&1\end{pmatrix}\stackrel{R_2-3R_1}\longrightarrow \begin{pmatrix}1&3/5&4/5\\0&21/5&-7/5\end{pmatrix}$$

From here we get

$$R_2\Longrightarrow \frac{21}{5}y=-\frac{7}{5}\Longrightarrow 21y=-7\stackrel{\text{if}\,\,p\neq 3}\Longrightarrow y=-\frac{7}{21}=-\frac{1}{3}$$

and then

$$R_1\Longrightarrow x+\frac{3}{5}y=\frac{4}{5}\Longrightarrow x=\frac{4}{5}+\frac{3}{5}\frac{1}{3}=1$$

and the solution for $\,p\neq 3,5\,$ is $\,\displaystyle{\left(1\,,\,-\frac{1}{3}\right)}\,$

When $\,p=3\,$ the system is clearly inconsistent (watch thesecond equation!), whereas for $\,p=7\,$ , as the reduction process we carried on above shows at the end in the second row $\,(0\,,\,0\,,\,0)\,$ , we get one single (linearly independent) equation in two unknowns and thus there are several solutions: each pair of the form

$$\left(x\,,\,y\right)\,\,\,,\,\,s.t.\,\,\,5x+3y=4\pmod 7$$

-
Glad to see that you noticed and fixed both errors (presumably after comparing to my answer). I had posted a comment to inform you of the errors right after posting my answer, but it seems it did not post (network timeout?) –  Bill Dubuque Sep 18 '12 at 0:19
Yeah...so gracious of you to comment it here now. –  DonAntonio Sep 18 '12 at 0:21
I'm disappointed that I lost said comment, since it included some useful tips, some being: $\:\rm(x,y) = (39/11,-11/21)\:$ cannot be a solution for $\rm\:p\neq 3,5,7\:$ since it is singular for $\rm\:p = 11.\:$ Further, a singularity cannot exist at $\rm\:p=11\:$ since the determinant $= 21\:$ is coprime to $11.\:$ Also, a fraction with denominator $105$ cannot reduce to one with denominator $11$ since $\rm\:11\nmid 105 = 3\cdot 5\cdot 7.$ These are all useful things to check when performing calculations like this. –  Bill Dubuque Sep 18 '12 at 0:42

Note $\rm\ 2\,(1)\! -\! (2)\to 7\,x = 7.\:$ $\rm\ x = 1\:$ in $\rm(1)\to 3\,y=-1,\:$ so $\rm\:(x,y) = (1,-\frac{1}3)\:$ is a solution if $\rm\:p\ne 3.\:$ Else $\rm\:p = 3\:$ so $\,(2)\,$ is $\rm\:1 = 3\,x+6\,y\equiv 0.\:$ Thus no solutions exist $\rm\iff p = 3.\ \$ QED

Note $\$ Since one of the coefficients of $\rm\,y\,$ is a multiple of the other, i.e. $\rm\:3\:|\:6,\:$ this makes it easy to eliminate $\rm\,y.\:$ That's why I chose to eliminate $\rm\,y\,$ rather than $\rm\,x.\,$ This is not true for $\rm\,x,\,$ so it is more work to eliminate $\rm\,x\,$ (see the other answer), leading to more complex arithmetic, so increasing the chance of errors. Such preprocessing often goes a long way towards simplifying such calculations, so it is well-worth looking for such optimizations before diving head-first into calculations.

-