# Chinese Remainder theorem with non-pairwise coprime moduli proof

There exists a $x \in \mathbb{Z}$ satisfying system of equations: $$x=a_1 \pmod {n_1}$$ $$x=a_2 \pmod {n_2}$$ $$\ldots$$ $$x=a_k \pmod{n_k}$$ if and only if $a_i=a_j \pmod{\gcd(n_i,n_j)}$ for all $i,j=1,...,k$?

Can anyone give me a proof by induction?

• @Mathmo123 I've tried proving the base case but I can't even do that – user108605 Aug 28 '14 at 10:31
• What did you try to do? Can you do it if $n_1, n_2$ are coprime? – Mathmo123 Aug 28 '14 at 10:33
• @Mathmo123 yes. Could you give me like half the proof? – user108605 Aug 28 '14 at 10:34

This is (almost) a duplicate of an already asked question. No matter, the proof I am going to give
is different from the one provided there.

$\qquad$Note that the algorithm does its job without ever needing to find the prime factorization of an integer (which can be time consuming).
$\qquad$Note also that we can omit the initial checking of conditions $(2)$ and instead do the checking on the fly. At each step we consider the subsistem consisting of the first two congruences of the current system, say $x\congr a\mod{m}$ and $x\congr b\mod{n}$; if $a\not\congr b\mod{\gcd(m,n)}$, we report that the system is unsolvable, otherwise we replace the two congruences with a single congruence $x\congr c\mod{\lcm(m,n)}$.

I'll give you some hints for the inductive step (note that the base case is actually when k=1 and is trivial).

Let $d= \operatorname{gcd}(n_1, n_2)$.

Note that if $$x\equiv a_1 \pmod {n_1}\\x\equiv a_2 \pmod {n_2}$$ has a solution, then in particular the solution must satisfy both of $$x \equiv a_1 \pmod d\\x \equiv a_2 \pmod d$$ Can you use this to get the required condition on $a_1$ and $a_2$ modulo $d$?

Now suppose $a_1 \equiv a_2 \pmod d$. Then $a_2 = a_1 + md$ for some $m \in \mathbb Z$. Let $y = x-a_1$. Then your equations are equivalent to $$y = 0 \pmod {n_1}\\ y = md \pmod{n_2}$$

Let $z = \frac yd$. Then these equations are equivalent to $$z \equiv 0 \pmod {\frac{n_1}d}\\z\equiv m \pmod {\frac{n_2}d}$$

Can you use this and the Chinese Remainder Theorem to get a solution for $x$?