Prove the congruence of RSA: $C^d\equiv M\ (\textrm{mod}\ pq)$ still hold even if $gcd(M, pq) > 1$.

Question

Pre-conditions:

Let the public key be $(n, e)$, and $n=pq$, which $p,q$ are large distinct primes. Let $gcd(e, (p-1)(q-1))=1$, and $d$ is the inverse of $e$ modulo $(p-1)(q-1)$.

And let $M$ be the raw message, $M < pq$, and $C$ represents the encrypted message(i.e. $M^e$).

---

Proof:

Since $M < pq$, and $p, q$ are prime, $gcd(M, pq) > 1$ implies that $gcd(M, p)=p$ or $gcd(M,q)=q$, but not both.

WLOG, consider the case $gcd(M, p)=p$ and $gcd(M, q)=1$. Let $ed=1+k(p-1)(q-1)$, then we have:

1. $C^d \equiv (M^e)^d \equiv 0\ (\textrm{mod}\ p) \equiv M\ (\textrm{mod}\ p)$
2. $C^d \equiv (M^e)^d \equiv M\cdot M^{k(p-1)(q-1)} \equiv M\cdot1^{k(p-1)} \equiv M\ (\textrm{mod}\ q)$

Since $gcd(p,q)=1$, $C^d \equiv M\ (\textrm{mod}\ pq)$ by Chinese Remainder Theorem. $\mathbf{Q.E.D.}$

---

This is an exercise in my text book Discrete Mathematics and it's Application, Rosen, page 305, section 4.6. And I don't have the solution...

Answer 1

my answer here covers this case too, and uses the same strategy. It's essentially the same argument, so I'd say the proof works.