Equation system modulo prime

Question

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?

Answer 1

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$.

Answer 2

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$.

Answer 3

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$