Chinese Remainder Theorem

Let $p$ and $q$ be positive integers such that $\mathrm{g}\mathrm{c}\mathrm{d}(p,q)=1$.

For two integers $x$ and $y$, there exists an integer $a$ such that

$\begin{array}{rl}a& \equiv xmodp\\ a& \equiv ymodq\end{array}$

if $b$ satisfies the same equivalences as $a$ above, then

$a\equiv bmodpq$

Namely,

$a\equiv xq\left(\frac{1}{q}(\mathrm{mod}p)\right)+yp\left(\frac{1}{p}(\mathrm{mod}q)\right)(\mathrm{mod}pq)$

Proof

Since $\mathrm{g}\mathrm{c}\mathrm{d}(p,q)=1$, there exist integers $p^{\prime }$ and $q^{\prime }$ such that

$\mathrm{g}\mathrm{c}\mathrm{d}(p,q)=1=p{p}^{\prime }+q{q}^{\prime }$

In particular, we have

$\begin{array}{r}q{q}^{\prime }\equiv 1modp\\ p{p}^{\prime }\equiv 1modq\end{array}$

Multiply both sides of the equivalence by $x$ and $y$ respectively…

$\begin{array}{r}xq{q}^{\prime }\equiv xmodp\\ yp{p}^{\prime }\equiv ymodq\end{array}$

The integer $a$ represents the sum of these two equivalences.

$a=yp{p}^{\prime }+xq{q}^{\prime }$

This is true because

$\begin{array}{c}yp{p}^{\prime }+xq{q}^{\prime }\equiv 0+xmodp\\ yp{p}^{\prime }+xq{q}^{\prime }\equiv y+0modq\end{array}\therefore \begin{array}{c}a\equiv xmodp\\ a\equiv ymodq\end{array}$

Suppose another integer $a^{\prime }$ also satisfies the equivalences above:

$\begin{array}{c}{a}^{\prime }\equiv xmodp\\ a^{\prime }\equiv ymodq\end{array}$

Therefore for some $k$

$a\equiv a^{\prime }modp⟶a-a^{\prime }=kp$

However, $a-a^{\prime }$ is divisible by both $p$ and $q$, which means that $kp$ must also be divisible by $q$.

$\begin{array}{rlr}kp& \equiv 0modp& \text{obviously}\\ kp& \equiv 0modq\end{array}$

$p$ and $q$ are coprime ($\mathrm{g}\mathrm{c}\mathrm{d}(p,q)=1$; they do not divide each other), so the second equivalence implies that $k$ must be divisible by $q$.

Therefore, $a-a^{\prime }$ must be divisible by $pq$, so as claimed,

$a\equiv a^{\prime }modpq$

Q.E.D.