Why does Gaussian elimination sometimes work in rings where it should not?

Question

I think it's best to illustrate this with an example.

Take for instance the ring of integers modulo $6$. If I have the system of equations:

$$ \begin{aligned} 2x + 2y &= 4 \\ 3x + 4y &= 3 \end{aligned} $$

I divide the first equation by $2$:

$$ \begin{aligned} x + y &= 2 \\ 3x + 4y &= 3 \end{aligned} $$

Subtract $3$ times the first equation from the 2nd equation to arrive at a solution for $y$:

$$ \begin{aligned} x + y &= 2 \\ 0 + y &= 3 \end{aligned} $$

Thus, $y = 3$ and $x = 5$.

From my understanding, this should be not possible as in ${\Bbb Z}_6$ there is no equivalence to $\frac12$ as $2$ does not have a multiplicative inverse in this ring, but yet I get a solution that works.

The best answer I have is that this is just a particular example in which dividing by $2$ was possible from construction, even if it makes no sense in the ring. I know I can invent situations where this would not be possible, for instance, if equation 1 was:

$$ 1x +3y = 1 $$

I'm curious if there is anything else at play here, or if it's just luck of construction that an answer could be found.

Answer 1

It's clearer triangularized: by (fraction-free) Gaussian elimination the system is equivalent to

$$\begin{align} x\ &=\ 5\\ 2y\ &= -6\end{align}\qquad$$

But $\,2y \equiv -6 \equiv 0 \pmod{\!6}\iff y \equiv 0\pmod{\!3}\iff y\equiv 0,3\pmod{\!6}\,$ by here.

Essentially you missed the solution $\,y\equiv 0\pmod{\!6}$ due to improper modular cancellation, i.e. not cancelling $\color{#c00}2$ everywhere (i.e. from the modulus too), as explained in the prior link, i.e.

$$\begin{align} \color{#c00}2y&\equiv \color{#c00}2\cdot 0\pmod{\color{#c00}2\cdot 3}\\ \iff\ y&\equiv\ \ \ \ \ 0\pmod{\ \ \ \ 3}\end{align}\qquad$$

or, divisibility-wise: $\,\color{#c00}2\cdot 3\mid \color{#c00}2y-\color{#c00}2\cdot 0\iff 3\mid y-0\,$ by cancelling $\color{#c00}2,\,$ i.e. $\,6\mid 2y\iff 3\mid y.$

Remark $ $ Generally your wrong inference is $\,nx\equiv na\pmod{\!nm}\iff x\equiv a\pmod{\!nm},\,$ but correct is $\,x\equiv a\pmod{\!m},\,$ so $\,\color{#0a0}{x\equiv\, a},\ a\!+\!m,\ a\!+\!2m,\ldots, a+(n\!-\!1)m\pmod{\!nm},\,$ so your wrong inference yields only one of the $\,n\,$ solutions $\!\bmod nm,\,$ viz. $\,\color{#0a0}{x\equiv a}\pmod{\!mn}$.

The "reason why it works" is that the direction $\,x\equiv a\pmod{\!mn}\,\Rightarrow\, nx\equiv na\pmod{\!mn}\,$ is always true. This multiplication (scaling) is a special case of the Congruence Product Rule. It's the cancellation in the opposite direction $(\Leftarrow)$ that fails without cancelling from the modulus too.

Answer 2

Equality is much stronger than congruence. If you find a solution and you are able to state that $x=x_o$ and $y=y_o$ and they are in $\mathbb{Z}$, they will clearly satisfy a modular version of the original equation.

It is a coincidence that the solution is indeed in $\mathbb{Z}$ though. And it could be that there are other solutions if you consider the weaker modular version.

Answer 3

The unique solution in $\Bbb Z$ gives of course a solution in $\Bbb Z_6.$ But your "dividing by 2" made you lose a second solution mod 6: $x=5,y=0.$

In $\Bbb Z_6,$ your initial system clearly determines only $2y,$ not $y.$

It can be solved without this faulty division as follows, applying Gaussian elimination more carefully: $$\begin{align}\begin{cases} 2x + 2y &\equiv4\bmod6 \\ 3x + 4y &\equiv3\bmod6 \end{cases}&\iff \begin{cases} 2x + 2y &\equiv4\bmod6\\ (3x + 4y)-2(2x+2y) &\equiv-5\bmod6 \end{cases}\\&\iff \begin{cases} 2x + 2y &\equiv4\bmod6\\x&\equiv5\bmod6 \end{cases}\\&\iff \begin{cases}2y &\equiv0\bmod6\\x&\equiv5\bmod6,\end{cases}\end{align}$$ and $$2y\equiv0\bmod6\iff y\equiv0\text{ or }3\bmod6.$$

Answer 4

If you multiply the equation $2x + 2y = 4 \pmod 6$ by $\frac12$, you should get $x+y=2\pmod 3$, or equivalently:

$$ \begin{cases} x+y=2,\text{or} \\ x+y=5 \end{cases} $$

You miss the second equation and consequently, another solution to the original equation system.

Answer 5

Let ${\Bbb Z}_6 := \left( \{0, 1, \dots, 5 \}, +, \cdot \right)$ be a finite ring. Consider the following system of linear equations over ${\Bbb Z}_6$.

$$ \begin{aligned} 2x + 2y &= 4 \\ 3x + 4y &= 3 \end{aligned} $$

Adding the 2nd equation to the 1st one,

$$ \begin{aligned} 5x + 0y &= 1 \\ 3x + 4y &= 3 \end{aligned} $$

because $2 + 4 = 0$ and $4 + 3 = 1$. Multiplying the 1st equation by $3$ and adding it to the 2nd one,

$$ \begin{aligned} 5x + 0y &= 1 \\ 0x + 4y &= 0 \end{aligned} $$

because $3 \cdot 5 = 3$ and $3 + 3 = 0$. Consulting the multiplication table for ${\Bbb Z}_6$, because $5 \cdot 5 = 1$ and $4 \cdot 0 = 4 \cdot 3 = 0$, we obtain $\color{blue}{x = 5}$ and $\color{blue}{y \in \{0,3\}}$.

---

Matrices

Working with augmented and elementary matrices instead, we obtain the following quasi-RREF

$$ \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 2 & 4 \\ 3 & 4 & 3 \end{bmatrix} = \begin{bmatrix} 5 & 0 & 1 \\ 0 & 4 & 0\end{bmatrix} $$

Note that all entries of these matrices are in the finite ring ${\Bbb Z}_6$. No $\frac12$ to be found.

---

Tables

The addition and multiplication tables for ${\Bbb Z}_6$ are as follows.

$$ \begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1\end{array} $$

Alternatively, $\TeX$ code can be found here.