Effective formula for the Chinese Remainder Theorem By the Chinese Remainder Theorem, we can find three numbers $j$, $k$, and $i$ such that $0 < j < p$, $0 < k < q$, $i \equiv j \pmod p$, $i \equiv k \pmod q$, $p$ and $q$ are prime and $i < pq$.
Finding $j$ and $k$ based on $i$ (given $p$, $q$) is relatively simple, but finding $i$ based on $j$ of $k$ is not.
I just need to prove that the following formula works. Any pointers?
$$i = \{j \cdot q \cdot (q^{-1} \bmod p) + k \cdot p \cdot (p^{-1} \bmod q)\} \bmod pq$$
Thank you!
 A: It is easy to verify. Write $\rm\,x\,$ for $\rm\,i,\,$ as is custom, and $\rm\:p' = (p^{-1}\, mod\ q)\ $ [exists by $\rm\,p,q\,$ coprime]
Then the formula gives $\rm\ mod\ p\!:\,\ x\, \equiv\, j\, q\, q^{-1}\! + k\, p\,p'\, \equiv\, j\cdot 1 + k \cdot 0\cdot p' \equiv j$
Similarly (by symmetry), $\rm\: mod\ q\!:\ x \equiv k.$ The solution is unique mod $\rm\:pq\:$ since if $\rm\:x,x'\:$ are solutions then $\rm\:x\equiv x'\:$ both mod $\rm\:p\:$ and $\rm\:q,\:$ so $\rm\:p,q\,|\,x-x'\:$ so $\rm\:lcm(p,q)\,|\,x-x',\:$ but $\rm\:lcm(p,q) = pq\:$ by $\rm\:p,q\:$ coprime, so $\rm\:pq\,|\,x-x',\:$ i.e. $\rm\:x\equiv x'\ (mod\ pq).$
In practice it is often more convenient to use a less symmetric solution, e.g.
Theorem $\:$ (Easy CRT) $\rm\ \ $ If $\rm\ p,q\:$ are coprime integers then $\rm\ p^{-1}\, $ exists $\rm\ (mod\ q)\  $ and
$\rm\displaystyle\quad\quad\quad\quad\quad \begin{eqnarray}\rm x&\equiv&\rm\,\ j\,\ (mod\ p) \\
\rm x&\equiv&\rm\ k\,\ (mod\ q)\end{eqnarray} \ \iff\ \ x\ \equiv\ j + p\: \bigg[\frac{k-j}{p}\ mod\ q\:\bigg]\ \ (mod\ pq)$
Remark $\ $ The key idea is that $\rm\:p(p^{-1}\ mod\ q)\:$ is $\rm\:\color{#C00}0\ mod\ p\:$ and $\rm\:\color{#0A0}1\ mod\ q,\:$ and, complementarily $\rm\:q(q^{-1}\ mod\ p)$ is $\rm\:\color{#C00}1\ mod\ p\:$ and $\rm\:\color{#0A0}0\ mod\ q.\:$  So mod $\rm\:p\!:\ x  \equiv j(\color{#C00}1)+k(\color{#C00}0)\equiv j,\:$ and $\rm\:mod\ q\!:\ x\equiv j(\color{#0A0}0) + k(\color{#0A0}1)\equiv k.\:$ This structure will be clearer if you study ring theory, where you'll learn about the key role such idempotents play in factorizations (look up Peirce decomposition).
