Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
You need the assumption that $p, q$ are primes, or at least coprime to each other. –  Calvin Lin Feb 1 '13 at 22:01
1  
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$). –  Henning Makholm Feb 1 '13 at 22:03
    
Sorry, updated for p & q prime. I just need to prove that the given formula works. Any ideas? –  Plastech Feb 1 '13 at 22:11

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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