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!

  • 1
    $\begingroup$ You need the assumption that $p, q$ are primes, or at least coprime to each other. $\endgroup$ – Calvin Lin Feb 1 '13 at 22:01
  • 1
    $\begingroup$ Finding $i$ given $j$ and $k$ is not "in reverse" -- it is what the Chinese Remainder Theorem is all about! (There's no commonly used name for the trivial fact that given $i$ you can compute its remainder modulo $p$ and $q$). $\endgroup$ – Henning Makholm Feb 1 '13 at 22:03
  • $\begingroup$ Sorry, updated for p & q prime. I just need to prove that the given formula works. Any ideas? $\endgroup$ – Plastech Feb 1 '13 at 22:11

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.