<s>[INST] Does the method of substitution always work for solving linear congruence systems? By substitution, I mean if I had this example:
$$  x \equiv 1 \pmod{5}$$ $$x \equiv 2 \pmod{6}$$
Then I would solve it by solving this equation...
$$ x = 1 + 5k \equiv 2 \pmod{6}$$ 
$$k \equiv 4 \pmod{6}$$
From this, I can substitute k back in for x...
$$x = 1 + 5(4 + 6m)$$
$$x = 21 + 30m$$
Meaning that...
$$x \equiv 21 \pmod{30}$$ (systems with more congruences would be solved by continuing this same process...)
It appears to work even if the moduli are not coprime, unlike one method of the Chinese Remainder Theorem. However, does it work for all systems? If so, please include a mathematical proof/explanation of why. 
If not, please include a counterexample showing that it doesn't work.
 [/INST] DEFINITION $1.$ Let's say that the system of linear congruences
\begin{align}
     x &\equiv a \pmod A \\
     x &\equiv b \pmod B
\end{align}
is consistent if $a \equiv b \mod{\gcd(A,B)}$.

THEOREM $2.$ The system of linear congruences
\begin{align}
     x &\equiv a \pmod A \\
     x &\equiv b \pmod B
\end{align}
has a solution if and only if they are consistent.
PROOF.
Suppose that the system of congruences has a solution, $x$.
Let $G = \gcd(A,B)$. Then $A = mG$ for some integer $m$. So 
\begin{align}
    x \equiv a \pmod A
        &\implies x  = a + kA & \text{for some } k \in \mathbb Z\\
        &\implies x = a + kmG \\
        &\implies x \equiv a \pmod G
\end{align}
So $x \equiv a \pmod A \implies x \equiv a \pmod G$.
Similarly, $x \equiv b \pmod B \implies x \equiv b \pmod G$.
Hence we must have $a \equiv b \pmod{G}$ and we have shown that the system of linear congruences is consistent.
Now suppose that the system of linear congruences is not consistent.
Then $a \not\equiv b \pmod{G}$ Then we can't have $x \equiv a \pmod G$ and $x \equiv b \pmod G$. so the system on linear congruences cannnot have a solution.

COROLLARY $3.$ The family of linear congruences 
$\{ x \equiv a_i \pmod A_i\}_{i=1}^N$ has a solution if and only if every pair of linear congruences is consistent.

LEMMA $4.$ Let $\gcd(A, B) = G$. Then
$\left( \dfrac AG \right)^{-1} \left(\bmod \dfrac BG \right)$ exists.
PROOF.
Note that $\dfrac AG$ and $\dfrac BG$ are integers because $G$ divides both $A$ and $B$.
Since $\gcd(A, B) = G$, there must exists integers $u$ and $v$ such that
\begin{align}
    Au + Bv = G
        &\implies \dfrac AGu + \dfrac BGv = 1 \\
        &\implies \dfrac AGu = 1 - \dfrac BGv \\
        &\implies \dfrac AGu \equiv 1 \left(\bmod \dfrac BG \right) \\
        &\implies \left( \dfrac AG \right)^{-1}
         \equiv u \left(\bmod \dfrac BG \right) \\
\end{align}

THEOREM $5.$ If the system of linear congruences
\begin{align}
     x &\equiv a \pmod A \\
     x &\equiv b \pmod B
\end{align}
is consistent, then the substitution method works.
PROOF.
Suppose that the system of linear congruences is consistent. Again, let
$G = \gcd(A,B)$. Then we must have $a \equiv b \pmod G$. So $G = k(a-b)$ for some integer $k$. Note that $\dfrac AG$ and $\dfrac BG$ are both integers.
Then if $x \equiv a \pmod A$, then $x = a +mA$ for some integer $m$.
Using the substitution method, we get
\begin{align}
    x \equiv b \pmod B
        &\implies a + mA \equiv b \pmod B \\
        &\implies mA \equiv b - a \pmod B \\
        &\implies mA \equiv kG \pmod B \\
        &\implies mA = Bu + kG & \text{for some integer } u \\
        &\implies m\dfrac AG = \dfrac BGu + k \\
        &\implies m\dfrac AG \equiv k \left(\bmod \dfrac BG \right) \\
        &\implies m \equiv
         k \left( \dfrac AG \right)^{-1}
         \left(\bmod \dfrac BG \right) \\
        &\implies m = u + \dfrac BGv
         &\text{for some } u,v\in \mathbb Z \\
\end{align}
So there must exists integers $u$ and $v$ such that
\begin{align}
    x &= a +mA \\
      &= a +(u + \dfrac BGv)A \\
      &= (a + uA) + \dfrac{AB}Gv \\
      &= (a + uA) + \operatorname{lcm}(A,B)v \\
\end{align}
Note that we have just proved that $x \equiv b \pmod B$ and 
$ x= (a + uA) + \operatorname{lcm}(A,B)v$ implies that
$x \equiv a \pmod A$. Hence the substitution method works.  

Note that we have also proved this.
COROLLARY $6.$ If the system of linear congruences
\begin{align}
     x &\equiv a \pmod A \\
     x &\equiv b \pmod B
\end{align}
is consistent then the substitution method will produce an answer modulo $\operatorname{lcm}(A,B)$.

Using simple induction, we can finally prove this.
THEOREM $7.$ If the family of linear congruences 
$\{ x \equiv a_i \pmod A_i\}_{i=1}^N$ is pairwise consistent, then the substitution method will produce an answer modulo 
$\operatorname{lcm}\{A_i\}_{i=1}^N$.
</s>