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.

Let $p$ and $q$ be relative primes, $n$ positive integer.

Given

  • $n\bmod p$ and
  • $n\bmod q$

how do I calculate $n\bmod (pq)$ ?

share
4  
en.wikipedia.org/wiki/… –  pedja Apr 10 '12 at 11:26
    
You might also have a look at Easy CRT in some Bill Dubuque's posts. –  Martin Sleziak Apr 10 '12 at 11:30

3 Answers 3

up vote 3 down vote accepted

Since $p$ and $q$ are relatively prime, there are integers $a$ and $b$ such that $ap+bq=1$. You can find $a$ and $b$ using the Extended Euclidean algorithm. Then $n\equiv aps+bqr \bmod pq$ if $n\equiv r \bmod p$ and $n\equiv s \bmod p$.

As pedja mentioned, this is a constructive proof of the Chinese remainder theorem.

share
    
+1 for getting their first !!! –  hardmath Apr 10 '12 at 20:48

From the fact that $p,q$ are relatively prime, we can find coefficients $a,b$ such that:

$$ap + bq = 1$$

With these coefficients we can piece together a solution for n from its residues modulo $p$ and $q$. Say:

$$n \equiv r \mod p$$ $$n \equiv s \mod q$$

Then this works: $ n = sap + rbq $ since:

$$bq \equiv 1 \mod p$$ $$ap \equiv 1 \mod q$$

Of course the above expression for $n$ can be reduced modulo $pq$ without affecting the residues modulo $p$ and $q$.

share

One may use the Bezout identity $\rm\:a\:p + b\:q = 1\:$ obtained by the extended Euclidean algorithm. But, in practice, it's often more convenient to use the form below, e.g. see my Easy CRT posts.

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 n&\equiv&\rm\ a\ (mod\ p) \\ \rm n&\equiv&\rm\ b\ (mod\ q)\end{eqnarray} \ \iff\ \ n\ \equiv\ a + p\ \bigg[\frac{b-a}{p}\ mod\ q\:\bigg]\ \ (mod\ p\:\!q)$

Proof $\rm\ (\Leftarrow)\ \ \ mod\ p\!:\:\ n\equiv a + p\ (\cdots)\equiv a\:,\ $ and $\rm\ mod\ q\!:\:\ n\equiv a + (b-a)\ p/p \equiv b\:.$

$\rm\ (\Rightarrow)\ \ $ The solution is unique $\rm\ (mod\ p\!\:q)\ $ since if $\rm\ x',\:x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:p,q\:$ therefore $\rm\ p,\:q\ |\ x'-x\ \Rightarrow\ p\!\:q\ |\ x'-x\ \ $ since $\rm\ \:p,\:q\:$ coprime $\rm\:\Rightarrow\ lcm(p,q) = p\!\:q\:.\quad$ QED

share
    
The link goes to emptiness... –  I. J. Kennedy May 1 '13 at 0:02

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .