RSA explanation

Question

Let's say that we have the following RSA setup where $m = pq$, where $p$ and $q$ are distinct primes. In addition, let $d, e \in \mathbb{N}$ such that $d = e^{-1}$(mod $\phi(m)).$ If $M$ stands for a plain text, we let $C \equiv M^e$ (mod $m$), where $C$ is the cypher text. As long as gcd ($C, m) = 1$, $\implies$ $C^d \equiv M$ (mod $m$). It was also shown (lecture) that gcd ($C,m) = 1$ exactly when $gcd(M,m) = 1.$ What happens if, in an unfortunate manner, the message I want to send is not relatively prime to $m$? We know that this never really happens in practice because our choices for $p$ and $q$ are large that the probability of $M$ being divisible by either $p$ or $q$ is roughly about $0$. It could be that $p$ and $q$ were small such that this situation may arise, but RSA should still work (at least I hope it does). With no assumption on gcd$(C,m)$ whatsoever, I want to show that $C^d \equiv M$ (mod $p$), $C^d \equiv M$ (mod $q$), $C^d \equiv M$ (mod $m$). Keep in mind that I know very little about cryptography, but I'm fine working with aspects related to number theory.

Answer 1

I've given you the link of my past proof if you interested in the details. But in short:

The key part is $Chinese\ Remainder\ Theorem$ that makes sure the cipher text can modulo-uniquely be solved for the plaintext. And what makes the CRT works is that the modulus should be pairwise relatively prime. But we've already done this! Since we choose $p, q$ two very large primes, and clearly two primes are relatively prime!

And the answer of @Henno Brandsma in the link provides very good details about all of it, so you can also check he's answer!

Answer 2

If $n$ is square-free and $k>0$ with $k\equiv1\pmod{\phi(n)}$, then $a^k\equiv a\pmod n$ for all $a$. Indeed by the CRT, it suffices to check $a^k\equiv a\pmod p$ for each prime factor $p$ of $n$. This is clear if $p|a$ as both sides are $0\pmod p$. Otherwise $a^{p-1}\equiv1\pmod p$ and $(p-1)|\phi(n)|(k-1)$, so $a^{k-1}\equiv1\pmod p$ and again $a^k\equiv a\pmod p$.

In this case $m$ is square-free and $de\equiv1\pmod{\phi(m)}$, so $$ C^d\equiv M^{de}\equiv M\pmod m. $$