# Equation system modulo prime

I have an excercise, it is to solve $$9\equiv_{p}8k_1+k_2$$ $$32\equiv_{p}6k_1+k_2$$ $$45\equiv_{p}11k_1+k_2.$$ $k_2$ is easily eliminated from the equations but I don't know how to proceed from there, I don't think that's the right way to go. We can get $13\equiv 5k_1$ and see that $p$ cannot be greater than $15$ otherwise this never gets fullfilled. Actually this fact reduces the problem to an easily soluable "trial-and-error" problem but I would like to have a systematic way to solve the problem. Could I get any hints how to start?

• if $p=14$ then $13\equiv 5*11$, so $p$ can definitely be greater than $13$ Jan 27, 2015 at 19:51

You can use the general strategy of solving simultaneous equations. (This exposition is indebted to Bill Dubuque, who pointed out an error and encouraged me to add details. I have taken a different, more rigorous approach here than in my previous answer.)

Subtracting the second equation from the first gives us $$-23 \equiv_p 2k_1$$

Subtracting the second equation from the third gives us $$13 \equiv_p 5k_1$$

Taking the last equation minus twice its previous equation gives us $$59 \equiv_p k_1$$

Substituting that into the second given equation and solving gives us $$k_2 \equiv_p -322$$

Substituting both of those into the first equation gives $$32 \equiv_p 150$$

So $p$ divides $150-32=141=3 \cdot47$. Since $p$ is prime, $p=3$ or $p=47$.

Test those two solutions for $p$ with the values for $k_1$ and $k_2$. For each $p$ you can easily find smaller, positive values of $k_1$ and $k_2$.

• but how did you get $k_2=-322$? if I substitute $k_1=59$ into the first one I get $9\equiv 59\cdot 8 +k_2$ that is $k_2=-463$. Am I calculating wrong? one does get that if we substitute in the second one but then I will never arrive at $32\equiv_{p}150. what am I doing wrong? Jan 28, 2015 at 16:49 • ohh now I see. Ignore my previous comments and thanks Jan 28, 2015 at 16:54 • @Vinyl_coat_jawa: I made a typo: that should have been "substitute into the second equation". The first equation also works, but I wanted to get a small value for$k_2$. Your value of$-463$also works. I have corrected my typo. Jan 28, 2015 at 17:45 You have a linear system $$\begin{cases} 8k_1+k_2=9\\ 6k_1+k_2=32\\ 11k_1+k_2=45 \end{cases}$$ in the field with$p$elements. Let's look at the rank of the matrix: $$\begin{bmatrix} 8 & 1 & 9\\ 6 & 1 & 32\\ 11 & 1 & 45 \end{bmatrix}$$ whose determinant is$141=3\cdot47$. So, if$p$is neither$3$nor$47$, the rank of the complete matrix of the system is$3$and the system has no solution, by the Rouché-Capelli theorem. If$p=3$the matrix can be written $$\begin{bmatrix} 2 & 1 & 0\\ 0 & 1 & 2\\ 2 & 1 & 0 \end{bmatrix}$$ and a simple elimination gives the reduced row echelon form $$\begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{bmatrix}$$ so we have a unique solution$k_1\equiv_3 2$,$k_2\equiv_3 2$. If$p=47$, the elimination is not as easy. But$6\cdot 8=48$, so we can multiply the first row by$6$, getting (remember we're working modulo$47$): $$\begin{bmatrix} 1 & 6 & 7 \\ 6 & 1 & 32 \\ 11 & 1 & 45 \end{bmatrix}$$ Subtract the first row multiplied by$6$from the second row and the first row multiplied by$11$from the third row, getting $$\begin{bmatrix} 1 & 6 & 7 \\ 0 & 12 & 37 \\ 0 & 29 & 15 \end{bmatrix}$$ Since$12\cdot4=\equiv_{47}1$, we can multiply the second row by$4$: $$\begin{bmatrix} 1 & 6 & 7 \\ 0 & 1 & 7 \\ 0 & 29 & 15 \end{bmatrix}$$ and now we can subtract the second row multiplied by$29$from the third row, getting $$\begin{bmatrix} 1 & 6 & 7 \\ 0 & 1 & 7 \\ 0 & 0 & 0 \end{bmatrix}$$ Now subtract the second row multiplied by$6$from the first row, getting $$\begin{bmatrix} 1 & 0 & 12 \\ 0 & 1 & 7 \\ 0 & 0 & 0 \end{bmatrix}$$ which means you have$k_1\equiv_{47}12$and$k_2\equiv_{47}7$. Hint$\ $Via (invertible) elementary row operations we obtain an equivalent triangular system$\ \begin{bmatrix} 1 & 8 & 9\\ 1 & 11 & 45\\ 1 & 6 & 32\\ \end{bmatrix} \leftrightarrow \begin{bmatrix} 1 & 8 & 9\\ 0 & 3 & 36\\ 0 & -2 & 23\\ \end{bmatrix} \leftrightarrow \begin{bmatrix} 1 & 8 & 9\\ 0 & 1 & 59\\ 0 & -2 & 23\\ \end{bmatrix} \leftrightarrow \begin{bmatrix} 1 & \color{}8 & \color{}9\\ 0 & 1 & \color{}{59}\\ 0 & 0 & \color{}{141}\\ \end{bmatrix} \leftrightarrow\!\! \begin{array}{r} k_2\!+ \color{#c00}8 k_1\, \equiv\ \ \color{#c00}9\\ k_1 \equiv\ \color{#0a0}{59}\\ 0 \equiv \color{blue}{141} \end{array} $Thus$\ 0 \equiv \color{blue}{141} = 3\cdot 47,\, $so$\, p = 3\,$or$\,47.\,$Back-substituting in each case yields$\qquad\ \ p\ =\ 3\ \Rightarrow\ k_1\equiv \color{#0a0}{59} \equiv \color{#0a0}{-1},\ \ k_2 \equiv\, \color{#c00}{9-8}\color{}{k_1} \equiv\, 0+1(\color{#0a0}{-1})\equiv\, {-}1\qquad\ \ p=47\ \Rightarrow\ k_1 \equiv \color{#0a0}{59}\equiv\, \color{#0a0}{12},\, \ \ k_2\equiv\, \color{#c00}{9-8}k_1\equiv\, 9-2\cdot 4\cdot \color{#0a0}{12}\,\equiv\, 9-2\equiv 7\$