Chinese remainder theorem - RSA The following is a excerpt from RSA Decryption correctness proof (section 4) :

$$\begin{align}
C^d &\equiv M\pmod {p} \tag{1}\\
C^d &\equiv M\pmod {q} \tag{2}
\end{align}$$
  Now by the Chinese Remainder Theorem, since $\gcd(p, q) = 1$ ($p$ and $q$ are
  different primes), there is exactly one number mod $pq$ that has properties
  $(1)$ and $(2)$ – it is $M \pmod{pq}$. So $C^d\equiv M\pmod {pq}$.

Question : How is that number $M\pmod {pq}$ ?
 A: $M$ is an integer. Suppose $X$ is some integer with the property that
$$X\equiv M\bmod p,\qquad X\equiv M\bmod q.$$
The Chinese remainder theorem then says that if $Y$ is any integer such that
$$Y\equiv M\bmod p,\qquad Y\equiv M\bmod q$$
then $Y\equiv X\bmod pq$. But obviously, $M$ is an integer with the property that
$$M\equiv M\bmod p,\qquad M\equiv M\bmod q.$$
Therefore, any $Y$ such that
$$Y\equiv M\bmod p,\qquad Y\equiv M\bmod q$$
must satisfy $Y\equiv M\bmod pq$.
A: $p$ and $q$ being two different primes, there exists two integers $m,n$ such that
$$
 mp-nq=1
$$
Your two equations can also be rewritten 
$$
 C^d = M +\alpha p \\
 C^d = M + \beta q
$$
Multiplying the first by $-nq$ and the second by $mp$ and summing them, we get 
$$
 (mp-nq)C^d = (mp-nq)M + (\beta m-\alpha n)pq
$$
And now returning to a modular expression you get
$$
 C^d = M \mod {pq}
$$
A: As $gcd(p,q) =1$, we have a group isomorphism
$$
\pi: \mathbb Z / pq \rightarrow \mathbb Z / p \times \mathbb Z / q, \ x + pq \mathbb Z \mapsto (x + p \mathbb Z, x + q \mathbb Z)
$$
You're looking for some $M + pq \mathbb Z \in \mathbb Z$ that satifies $\pi (M + pq \mathbb Z) = (C^d + p \mathbb Z, C^d + q \mathbb Z)$. By the above such a value $M$ exists and is unique. 
