I have the following system of linear congruences:
\begin{align}
x&\equiv -2 \pmod {6}\\
x&\equiv 2 \pmod {10}\\
x&\equiv 7 \pmod {15}
\end{align}
From the first equation we have: $ x= 6 k-2, k\in \mathbb{Z}$. Then we insert it into 2nd equation:
$ 6 k -2 \equiv 2 (\mod 10) $ i.e. $ 6 k \equiv 4 (\mod 10) $
from which we obtain
$ 3 k \equiv 2 (\mod 5) $
Now at this point, is it allowed to multiply the last congruence by 2 to get:
$ k \equiv -1 (\mod 5) $
and conclude $k = 5 l -1, l\in \mathbb{Z}$ and $ x = 30 n -8 , n\in \mathbb{Z}$ ?
I wonder if this is correct, is the obtained congruence equivalent to the first one? Thanks in advance.
Best Answer
One must indeed be very careful to correctly keep track of implications in derivations like this. The key idea of this form of CRT is that we can solve a system of congruences by successively replacing a pair of congruences by an equivalent congruence, till we reach a single congruence. Thus it is essential to be sure that the replacement for each pair remains equivalent at each step.
So, e.g. in your case we seek to replace your first two congruences by the equivalent one below
$$\begin{align} x&\equiv -2\!\!\pmod{6}\\ x&\equiv\ \ \ 2\!\pmod{10}\end{align}\iff x\equiv -8\!\!\pmod{\!30}$$
There are a couple ways to prove that equivalence. First we could use all unidirectional inferences $(\Rightarrow)$ in our intermediate steps to obtain a proof of the direction $(\Rightarrow),\,$ then we could prove the direction $(\Leftarrow)$ by simply checking that $\,x\equiv 8\pmod{30}\,$ is actually a root of the two LHS congruences.
However this is actually not needed because every step of this (standard) method of CRT solution of a pair of congruences is actually an equivalence. Below I show the intermediate steps in detail.
$$\begin{align} &\ x\equiv -2\!\!\!\pmod{\!6},\ \ x\equiv 2\!\!\!\pmod{\!10}\\[.2em] \iff\ &\exists k\!:\, x = -2+6k,\ \ x\equiv 2\!\!\!\pmod{\!10}\\[.2em] \iff\ &\exists k\!:\, x = -2+6k,\ {-}2+6k\equiv 2\!\!\!\pmod{\!10}\\[.2em] \iff\ &\exists k\!:\, x = -2+6k,\ \ k\equiv -1\!\!\!\pmod{\!5}\\[.2em] \iff\ &\exists k\!:\, x = -2+6k,\ \exists n\!:\, k = -1+5n\\[.2em] \iff\ &\exists n\!:\, x = -2+6(-1+5n) = -8+30n\\ \iff\ &\, x\equiv -8\!\!\!\pmod{\!30} \end{align}$$
Remark $ $ For more on the ramifications of insufficiency of unidirectional inferences here (esp. its manifestation as extraneous roots) see here and its links.