The Antifragile Chaos Monkey
It doesn't break down. Everything works modulo n=pq. You always need to choose encode your message M to be an interger < n. If you are worried that M will be zeroed out at some point, it won't, since even p mod(pq) will not be zero.
But the proof I saw for the decrypt(encrypt(M)) = M relied on Euler's Theorem, which relied on M being relatively prime to p and q. Is that just because I was seeing a simplified version of the real proof?
I thought I responded to this yesterday, but you either didn't publish it or it got lost in transmission.
You really want to use Fermat's little theorem (a particular case of Euler's theorem). Read the first proof here, and note that the second proof (which is probably what you saw) is not really a proof at all, for the reason you mentioned.