# If I want to use induction to prove Chinese Remainder Theorem, do I need to separate the proof into existence part and uniqueness part?

%%(Theorem A) For all $j\geq 3$, $n_j$ is relatively prime to the product of all the previous $n’s$.%%

%%(Theorem B) Let $a,b,m,$ and $n$ be integers with $m>0$ and $n>0$, and $(m,n)=1$. Then the system \begin{align*} x\equiv a\pmod n\\ x\equiv b\pmod m \end{align*} has a unique solution modulo $mn$.%%

Let $P(s)$ be "the system of $s$ congruences has a unique solution modulo the product $n_1n_2n_3\cdots n_s$".

I have proved that $P(2)$ is true.

Inductive Hypothesis: Suppose $k$ is an integer with $k \geq 2$ such that the system of $k$ congruences has a unique solution modulo the product $n_1n_2n_3 \cdots n_k$.

By Inductive Hypothesis, the system of $k$ congruences has a unique solution $x\equiv x_0 \pmod{n_1n_2n_3 \cdots n_k}$.

Suppose we have $x\equiv a_{k+1} \pmod {n_{k+1}}$.

Then, by Theorem A, $(n_{k+1}, n_1n_2n_3 \cdots n_k)=1$.

Hence by Theorem B, the system \begin{align*} x&\equiv x_0 \pmod{n_1n_2n_3 \cdots n_k}\\ x&\equiv a_{k+1} \pmod {n_{k+1}} \end{align*} has a unique solution modulo $n_1n_2n_3 \cdots n_{k+1}$

$P(k)\Rightarrow P(k+1)$.

$\therefore$ Chinese Remainder Theorem is true.

• See here for the general case when the moduli are not pairwise coprime. – Bill Dubuque Jun 26 '17 at 0:22

You are implicitly assuming that all the $n_j$ are pairwise coprime. The other is correct (when you use Th.B you already have existence and uniqueness at once).
• Oh, yes. You are right. This is part of my proof. In my original proof, I have assumed "$n_1, n_2, ..., n_s$ are positive integers that are pairwise relatively prime.". – user398843 Jun 25 '17 at 23:54