Chapter 4.6, Problem 28E

Suppose that (n, e) is an RSA encryption key, with $n=pq$ , where p and q are large primes and $\text{gcd}\left(e,\left(p-\text{1}\right)\left(q-\text{1}\right)\right)=\text{1}$ . Furthermore, suppose that d is an inverse of e modulo $\left(p-\text{1}\right)\left(q-\text{1}\right)$ . Suppose that $C\equiv M^2\left(\text{mod }pq\right)$ . In the text we showed that RSA decryption, that the congruence $c^d\equiv m\left(\text{mod }pq\right)$ holds when $\text{gcd}\left(M,pq\right)=\text{1}$ . Show that this decryption congruence also hold when $\text{gcd}\left(M,pq\right)>\text{1}$ . [Hint: Use congruences modulo p and modulo q and apply the Chinese remainder theorem.]