RSA: Prove/disprove that $M_1^e\equiv M_2^e\ (\textrm{mod}\ n),$ given $M_1\not=M_2$ Given that $M_1\not=M_2, n=pq$ where $p,q$ are large primes and $\gcd(e,\varphi(n))=1$, how to prove/disprove that
$$M_1^e\equiv M_2^e\ (\textrm{mod}\ n)$$
is impossible? That is: I'm thinking about the case that two distinct messages $M_1,M_2$ has the same encrypted-text $C=M_1^e\mod n=M_2^e\mod n$.
I've tried a proof that using CRT and lead to a contradiction $M_1=M_2$ but it is a little bit complicated so I want to know is there any possible (simpler) alternatives.
 A: I posted a proof here that RSA is a bijective map from $\mathbb{Z}_n$ to itself, provided that $(\phi(N),e) =1$, and where the message space is the set of classes modulo $N$, the modulus.
So if we assume (as we must) that we are working in that message set, the RSA mapping has an inverse (using the exponent $d$ as described) and is in particular injective. 
I also use the CRT, but why not? It's a basic tool in number theory. It's not "complicated".
A: Note that $\phi(n)=\phi(p)\phi(q)$. Assume that the given is possible for some $M_1\not\equiv M_2 \pmod{n}$. 
First suppose that $p,q\nmid M_1$. You will have that $p,q\nmid M_2$. Hence, using Fermat's theorem, you have $M_1^{p-1}\equiv 1\pmod{p}$, and $M_2^{p-1}\equiv 1\pmod{p}$. Now using $(e,\phi(n))=1$, we also deduce that $(e,p-1)=1$, hence there exists integers $a,b$ such that $ea+(p-1)b=1$. Using these integers, observe that,
$$
M_1^{e}\equiv M_2^{e}\pmod{p} \quad\text{and}\quad M_1^{p-1}\equiv M_2^{p-1}\pmod{p}\implies M_1^{ae+b(p-1)}\equiv M_2^{ae+b(p-1)}\pmod{p},
$$
namely, $M_1\equiv M_2\pmod{p}$ ,and similarly, $M_1\equiv M_2\pmod{q}$, however since $n\nmid M_1-M_2$, this is a contradiction.
The other case can also be handled similarly. 
