How do you solve linear congruences with three variables.

Question

Given

\begin{cases} x+y+z &\equiv 1 \pmod{10} \\ x+2y+3z &\equiv 2 \pmod{10} \\ 2x+3y+6z &\equiv 3 \pmod{10} \end{cases}

find $x,y,z$.

How does one solve such a system of equations?

Answer 1

We can use a slight variation on Gaussian elimination, bearing in mind that we don't want to multiply our rows by any scalars that aren't invertible modulo $10.$ We can rewrite our system of equations as a vector equation $$\begin{bmatrix}1x+1y+1z\\1x+2y+3z\\2x+3y+6z\end{bmatrix}\equiv\begin{bmatrix}1\\2\\3\end{bmatrix}\pmod{10},$$ which is the same as $$\begin{bmatrix}1 & 1 & 1\\1 & 2 & 3\\2 & 3 & 6\end{bmatrix}\begin{bmatrix}x\\y\\z\end{bmatrix}\equiv\begin{bmatrix}1\\2\\3\end{bmatrix}\pmod{10}.$$ Rewriting as an augmented coefficient matrix $$\left[\begin{array}{ccc|c}1 & 1 & 1 & 1\\1 & 2 & 3 & 2\\2 & 3 & 6 & 3\end{array}\right],$$ subtracting the first two rows from the third yields $$\left[\begin{array}{ccc|c}1 & 1 & 1 & 1\\1 & 2 & 3 & 2\\0 & 0 & 2 & 0\end{array}\right].\tag{$\star$}$$ Note that if we had started with the system $$\begin{cases}x+y+z\equiv1\pmod{10}\\x+2y+3z\equiv2\pmod{10}\\2x+3y+6z\equiv3\pmod{10},\end{cases}$$ and then subtracting the first and second equations from the third, then we would have the equivalent system $$\begin{cases}x+y+z\equiv1\pmod{10}\\x+2y+3z\equiv2\pmod{10}\\2z\equiv0\pmod{10},\end{cases}$$ which is the same as $$\begin{cases}1x+1y+1z\equiv1\pmod{10}\\1x+2y+3z\equiv2\pmod{10}\\0x+0y+2z\equiv0\pmod{10}.\end{cases}$$ Note that the coefficients of this new system match up precisely with the entries in $(\star)$, which is why this technique works. Now, looking again at $(\star)$, subtracting the first row from the second yields $$\left[\begin{array}{ccc|c}1 & 1 & 1 & 1\\0 & 1 & 2 & 1\\0 & 0 & 2 & 0\end{array}\right].$$ Next, we subtract the third row from the second to get $$\left[\begin{array}{ccc|c}1 & 1 & 1 & 1\\0 & 1 & 0 & 1\\0 & 0 & 2 & 0\end{array}\right],$$ whence subtracting the second row from the first yields $$\left[\begin{array}{ccc|c}1 & 0 & 1 & 0\\0 & 1 & 0 & 1\\0 & 0 & 2 & 0\end{array}\right].$$

Translated back into modular terms, this gives us the equivalent system $$\begin{cases}1x+0y+1z\equiv0\pmod{10}\\0x+1y+0z\equiv1\pmod{10}\\0x+0y+2z\equiv0\pmod{10},\end{cases}$$ or equivalently$$\begin{cases}x+z&\equiv 0\pmod{10}\\y&\equiv1\pmod{10}\\2z&\equiv0\pmod{10}\end{cases}{}{}{}$$ Can you take it from there?