Understanding why single-variable expansion of modular arithmetic is valid.

Question

I was reading: https://arxiv.org/pdf/1206.5114.pdf page 10 and came across an odd theorem.

It states, that the system:

$$ \begin{matrix} 2x_1+ 3x_2 \equiv 1 \mod 5 \\ 3x_1 + 5x_2 \equiv 1 \mod 7 \end{matrix} $$

Can be "re-written" as:

$$ \begin{matrix} 2x_1+ 3x_2 +5x_3 = 1 \\ 3x_1 + 5x_2 + 7x_3 = 1 \end{matrix} $$

Now what exactly is meant by "re-written here?" is it that for every solution in the first system there exists a solution in the second system? Or that for every solution in the second system there exists a solution in the first system? Or both?

I find at least the notion of "BOTH" to be impossible. For the simple reason that if we let $X = 2x_1 + 3x_2$ and let $Y = 3x_1 + 5x_2$

Then we are claiming that if

$$ X \equiv 1 \mod 5$$ $$ Y \equiv 1 \mod 7$$

That there exists an $x_3$ such that

$$ X + 5x_3 = 1 $$ $$ Y + 7x_3 = 1$$

Now to me this seems very odd, since if we analyze

$$ X \equiv 1 \mod 5$$

To me all that says is there is SOME integer $s$ such that $X = 5s + 1$ and similarly there is SOME integer $r$ such that $Y = 7r + 1$. The idea that $s = r$ is necessary seems blatantly false (let X = 11, Y = 8 as a counter example). With BOTH ruled out, (And our counter-example ruling out that every solution the first system implies a solution to the second system) it's pretty clear that at best every solution to the second system is a solution to first.

Now certainly I would call that a severe loss of information and not a simple "re-write", so does this paper have a mistake and they meant to communicate something else? or am I missing a major detail? or is the analysis up to here correct and the term "re-written" has a hidden loss of information not made clear by the paper.

Answer 1

The solutions to $$2x_1+3x_2+5x_3=1, 3x_1+5x_2+7x_3=1$$ satisfy $$2x_1+3x_2≡1, \mod5 $$

$$3x_1+5x_2≡1, \mod7$$

But the solutions to the second system are not necessarily solutions to the first system because you may have $$2x_1+3x_2+5x_3=1, 3x_1+5x_2+7x_4=1$$ where $x_3\ne x_4$

Answer 2

Now what exactly is meant by "re-written here?"

The expressions are equivalent. For a simpler example, consider:

$$4x_1 + 3x_2 \equiv 5 \pmod 6 \tag 1$$

I will write this expression in a similar way to that PDF file. Consider the definition of congruence in this context:

$$a \equiv b \pmod m \iff \frac{a-b}{m} = k \in \mathbb Z$$

Then $(1)$ becomes

$$4x_1 + 3x_2 \equiv 5 \pmod 6 \iff \frac{4x_1 + 3x_2 - 5}{6} = k \in \mathbb{Z} \tag 2$$

Multiply by $6$ on each side in $(3)$, add $5$ to each side, and subtract the integer $k$ from each to obtain

$$\frac{4x_1 + 3x_2 - 5}{6} = x_3 \in \mathbb{Z} \iff 4x_1 + 3x_2 -6k = 5 \tag 4$$

Since $k \in \mathbb{Z}$, we know an integer $-k$ exists. We can take $k = -x_3$ for some integers $x_3$ and thus $(4)$ becomes

$$4x_1 + 3x_2 -6k = 5 \iff 4x_1 + 3x_2 -6(-x_3) = 5 \iff 4x_1 + 3x_2 + 6x_3 = 5$$

---

Now, of course, the prior is something I think you're already aware of in some form, which you touch on. So I'll address another point:

Now to me this seems very odd, since if we analyze $$ X \equiv 1 \mod 5$$ To me all that says is there is SOME integer $s$ such that $X = 5s + 1$ [...]

While this is sort of true, solutions $X$ to a modular congruence as above are really just an equivalence class of integers. The "some integer" you're referring to is probably the "least residue" (at least, that's what I often find people misinterpret it as), but in this above equation there are multiple solutions because, per our definition of modular congruence,

$$X \equiv 1 \pmod 5 \iff \frac{X-1}{5} = k \in \mathbb{Z}$$

Or, less formally, solutions $X$ have a remainder $1$ when divided by $5$ (not the best definition, mind you, it's sometimes misleading to look at it that way). So which $X$ are a solution?

$$X = \{ ..., -9, -4, 1, 6, 9, ... \} = \{ k \in \mathbb{Z} | k = 5n, n \in \mathbb{Z} \} $$

This is an equivalence class of solutions, which we denote by $[1]$ (since $1$ is the least residue). All are solutions to the congruence.

In extrapolating this logic to a system of congruences, think of it like an ordinary system of equations. Many inputs could satisfy any of the equations (not necessarily one), and the system seeks only those that satisfy all of the equations (provided they exist). Similar idea at play here.