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? 
 A: 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$.
A: 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$.
A: 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$
