# Chinese remainder theorem proof

We first prove the following lemma: if

$$a\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(modp)$$ |

$$a\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(modq)$$ |

$$\mathrm{gcd}(p,q)=1$$ |

then

$$a\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(modpq)$$ |

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=\mathrm{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 $\mathrm{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\phantom{\rule{veryverythickmathspace}{0ex}}(modpq)$, 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\le i\le n$. If

$${y}_{i}\frac{P}{{p}_{i}}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{i})$$ |

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

$${y}_{i}\frac{P}{{p}_{i}}-1=k{p}_{i}$$ |

which in turn implies that

$${y}_{i}\frac{P}{{p}_{i}}-k{p}_{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 $\mathrm{gcd}(a,b)$ divides $c$. Since $\frac{P}{{p}_{i}}$ is the product^{} of each ${p}_{j}$ ($j\in \mathbb{N}$, $1\le j\le 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, $\mathrm{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\le j\le n$. For any $i\in \mathbb{N}$, $1\le i\le n$, either $i\ne j$ or $i=j$. If $i\ne 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\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{j})$$ |

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

$${y}_{j}\frac{P}{{p}_{j}}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{j})$$ |

so we know

$${a}_{j}{y}_{j}\frac{P}{{p}_{j}}\equiv {a}_{i}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{j})$$ |

So we have a set of $n$ congruences^{} $mod{p}_{j}$; summing them shows that

$$\sum _{i=1}^{n}{a}_{i}{y}_{i}\frac{P}{{p}_{i}}\equiv {a}_{i}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{j})$$ |

Therefore ${x}_{0}$ satisfies all the congruences.

Suppose we have some

$$x\equiv {x}_{0}\phantom{\rule{veryverythickmathspace}{0ex}}(modP)$$ |

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}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{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}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{i})$$ |

and since

$${x}_{0}\equiv {a}_{i}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{i})$$ |

the transitive and symmetric properties of congruence imply that

$$x\equiv {x}_{0}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{i})$$ |

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

$$x\equiv {x}_{0}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{1}{p}_{2}\mathrm{\dots}{p}_{n})$$ |

or

$$x\equiv {x}_{0}\phantom{\rule{veryverythickmathspace}{0ex}}(modP)$$ |

Title | Chinese remainder theorem proof |
---|---|

Canonical name | ChineseRemainderTheoremProof |

Date of creation | 2013-03-22 11:59:11 |

Last modified on | 2013-03-22 11:59:11 |

Owner | vampyr (22) |

Last modified by | vampyr (22) |

Numerical id | 7 |

Author | vampyr (22) |

Entry type | Proof |

Classification | msc 11D79 |