# Chinese remainder theorem proof

We first prove the following lemma: if

 $a\equiv b\pmod{p}$
 $a\equiv b\pmod{q}$
 $\gcd(p,q)=1$

then

 $a\equiv b\pmod{pq}$

We know that for some $k\in\mathbb{Z}$, $a-b=kp$; likewise, for some $j\in\mathbb{Z}$, $a-b=jq$, so $kp=jq$. Therefore $kp-jq=0$.

It is a well-known theorem that, given $a,b,c,x_{0},y_{0}\in\mathbb{Z}$ such that $x_{0}a+y_{0}b=c$ and $d=\gcd(a,b)$, any solutions to the diophantine equation $ax+by=c$ are given by

 $x=x_{0}+\frac{b}{d}n$
 $y=y_{0}+\frac{a}{d}n$

where $n\in\mathbb{Z}$.

We apply this theorem to the diophantine equation $kp-jq=0$. Clearly one solution of this diophantine equation is $k=0,j=0$. Since $\gcd(q,p)=1$, all solutions of this equation are given by $k=nq$ and $j=np$ for any $n\in\mathbb{Z}$. So we have $a-b=npq$; therefore $pq$ divides $a-b$, so $a\equiv b\pmod{pq}$, thus completing the lemma.

Now, to prove the Chinese remainder theorem, we first show that $y_{i}$ must exist for any natural $i$ where $1\leq i\leq n$. If

 $y_{i}\frac{P}{p_{i}}\equiv 1\pmod{p_{i}}$

then by definition there exists some $k\in\mathbb{Z}$ such that

 $y_{i}\frac{P}{p_{i}}-1=kp_{i}$

which in turn implies that

 $y_{i}\frac{P}{p_{i}}-kp_{i}=1$

This is a diophantine equation with $y_{i}$ and $k$ being the unknown integers. It is a well-known theorem that a diophantine equation of the form

 $ax+by=c$

has solutions for $x$ and $y$ if and only if $\gcd(a,b)$ divides $c$. Since $\frac{P}{p_{i}}$ is the product of each $p_{j}$ ($j\in\mathbb{N}$, $1\leq j\leq n$) except $p_{i}$, and every $p_{j}$ is relatively prime to $p_{i}$, $\frac{P}{p_{i}}$ and $p_{i}$ are relatively prime. Therefore, by definition, $\gcd(\frac{P}{p_{i}},p_{i})=1$; since $1$ divides $1$, there are integers $k$ and $y_{i}$ that satisfy the above equation.

Consider some $j\in\mathbb{N}$, $1\leq j\leq n$. For any $i\in\mathbb{N}$, $1\leq i\leq n$, either $i\neq j$ or $i=j$. If $i\neq j$, then

 $a_{i}y_{i}\frac{P}{p_{i}}=\left(a_{i}y_{i}\frac{P}{p_{i}p_{j}}\right)p_{j}$

so $p_{j}$ divides $a_{i}y_{i}\frac{P}{p_{i}}$, and we know

 $a_{i}y_{i}\frac{P}{p_{i}}\equiv 0\pmod{p_{j}}$

Now consider the case that $i=j$. $y_{j}$ was selected so that

 $y_{j}\frac{P}{p_{j}}\equiv 1\pmod{p_{j}}$

so we know

 $a_{j}y_{j}\frac{P}{p_{j}}\equiv a_{i}\pmod{p_{j}}$

So we have a set of $n$ congruences $\bmod\ p_{j}$; summing them shows that

 $\sum_{i=1}^{n}a_{i}y_{i}\frac{P}{p_{i}}\equiv a_{i}\pmod{p_{j}}$

Therefore $x_{0}$ satisfies all the congruences.

Suppose we have some

 $x\equiv x_{0}\pmod{P}$

This implies that for some $k\in\mathbb{Z}$,

 $x-x_{0}=kP$

So, for any $p_{i}$, we know that

 $x-x_{0}=\left(k\frac{P}{p_{i}}\right)p_{i}$

so $x\equiv x_{0}\pmod{p_{i}}$. Since congruence is transitive, $x$ must in turn satisfy all the original congruences.

Likewise, suppose we have some $x$ that satisfies all the original congruences. Then, for any $p_{i}$, we know that

 $x\equiv a_{i}\pmod{p_{i}}$

and since

 $x_{0}\equiv a_{i}\pmod{p_{i}}$

the transitive and symmetric properties of congruence imply that

 $x\equiv x_{0}\pmod{p_{i}}$

for all $p_{i}$. So, by our lemma, we know that

 $x\equiv x_{0}\pmod{p_{1}p_{2}\dots p_{n}}$

or

 $x\equiv x_{0}\pmod{P}$
Title Chinese remainder theorem proof ChineseRemainderTheoremProof 2013-03-22 11:59:11 2013-03-22 11:59:11 vampyr (22) vampyr (22) 7 vampyr (22) Proof msc 11D79