Chinese Remainder Theorem

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

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

${\begin{aligned}a&\equiv x\mod {p}\\a&\equiv y\mod {q}\end{aligned}}$

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

$a\equiv b\mod {pq}$

Namely,

$a\equiv x\,q\left({\frac {1}{q}}{\pmod {p}}\right)+y\,p\left({\frac {1}{p}}{\pmod {q}}\right){\pmod {p\,q}}$

Proof

Since $\mathrm {gcd} (p,q)=1$, there exist integers $p'$ and $q'$ such that

$\mathrm {gcd} (p,q)=1=pp'+qq'\,\!$

In particular, we have

${\begin{aligned}qq'\equiv 1\mod {p}\\pp'\equiv 1\mod {q}\end{aligned}}$

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

${\begin{aligned}xqq'\equiv x\mod {p}\\ypp'\equiv y\mod {q}\end{aligned}}$

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

$a=ypp'+xqq'\,\!$

This is true because

${\begin{matrix}ypp'+xqq'\equiv 0+x\mod {p}\\ypp'+xqq'\equiv y+0\mod {q}\end{matrix}}\quad \therefore \quad {\begin{matrix}a\equiv x\mod {p}\\a\equiv y\mod {q}\end{matrix}}$

Suppose another integer $a'$ also satisfies the equivalences above:

${\begin{matrix}a'\equiv x\mod {p}\\a'\equiv y\mod {q}\end{matrix}}$

Therefore for some $k$

$a\equiv a'\mod {p}\quad \longrightarrow \quad a-a'=kp$

However, $a-a'$ is divisible by both Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and $q$, which means that $kp$ must also be divisible by $q$.

${\begin{aligned}kp&\equiv 0\mod {p}&{\mbox{obviously}}\\kp&\equiv 0\mod {q}\end{aligned}}$

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

Therefore, $a-a'$ must be divisible by $pq$, so as claimed,

$a\equiv a'\mod {pq}$

Q.E.D.