Taking modulo by product of 2 primes If we are given a number $n$, and two primes $p_1$ and $p_2$, and we have $a = n$ modulo $p_1$ and $b = n$ modulo $p_2$, can $n$ modulo $p_1p_2$ be evaluated using $a$ and $b$?
 A: You are asking about a special case of the Chinese Remainder Theorem. (Please see the Wikipedia article, or any beginning book in Number Theory.)
Let us call the primes $p$ and $q$, and assume they are distinct. First find numbers $s$ and $t$ such that $qs \equiv 1\pmod p$ and $pt\equiv 1\pmod{q}$. For large $p$ and $q$, we can do this using the Extended Euclidean Algorithm. For small $p$ and $q$, one can often do it by inspection. 
Then 
$$n\equiv aqs+bpt\pmod {pq}.$$
We now verify that the above expression is correct. Note that $aqs+bpt\equiv aqs \pmod{p}$. But by the choice of $s$, we have $qs\equiv 1\pmod{p}$, so $aqs+bpt\equiv a \pmod{p}$. Similarly,  $aqs+bpt\equiv b \pmod{q}$.  
Note that once we have precomputed $s$ and $t$, they can be used for any given values of $a$ and $b$. 
A: The short answer is that if $x \equiv x_0\ (\text{mod}\ p_0)$ and $x \equiv x_1\ (\text{mod}\ p_1)$ then
$$x\equiv p_0*(p_0^{-1}\ \text{mod}\ p_1)*(x_1-x_0) \hspace{1em} (\text{mod}\ p_0p_1)$$
As André has already noted, this is a consequence of the Chinese Remainder Theorem, and more directly Garner's algorithm. Garner's algorithm works by assuming $x$ has the form $v_0+p_0v_1+p_0p_1v_2+\dots$ and using the residues to solve for the various $v_i$.
Concretely, if you have residues $xs=[x_0,x_1,\dots]$ and prime powers $m=p_0^{k_0} p_1^{k_1}\dots$ you may calculate $x\ \text{mod}\ m$ by the following simple procedure:
def garner(xs, ps, m):
    r, q = 0, 1
    for x, p^k in zip(xs, ps):
        r += q * inv(q, p^k) * (x - r)
        r %= m
        q *= p^k
    return r

Where $\text{inv}(n, p^k)$ returns the inverse of $n$ modulo $p^k$. (This can easily be calculated using fast exponentiation and Euler's formula as $n^{p^{k-1}(p-1)-1}\ \text{mod}\ p^k$).
