2
$\begingroup$

%%(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.

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

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).

$\endgroup$
1
  • $\begingroup$ 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.". $\endgroup$ – user398843 Jun 25 '17 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.