RSA:Plaintext block has a common factor with modulus I've seen a couple of posts stating the following fact: If $(n = pq,e)$ is the public key of an RSA instance and some plaintext block $m$ has a common factor with $n$, then also the corresponding ciphertext block $c$ has the same common factor with $n$.

Yet, I could not find any formal proof of this statement. I tried to come up with one by myself, but I could not quite make it. What I have so far: 

As $m&lt;n$, $m = p * z$ or $m = q*z$ for some $z \in \mathbb{Z}$. Assume w.l.o.g $m = p * z$. Then $c = m^e \mod n = (p * z)^e \mod n$. I don't really know how to continue. One could rewrite this further as $c = ((p^e \mod n)  * (z^e \mod n)) \mod n$ but that didn't help me either. Does someone have a hint for me?

Any help is appreciated! Thank you.
Here's one way to argue for this property using the Chinese Remainder Theorem:

Let $m,e,n=pq$ be arbitrary with $\gcd(p,q)=1$. Let's assume $\gcd(m,n)&gt;1$ and more precisely wlog $\gcd(m,n)=p$. Now we shall apply the Chinese Remainder Map $\theta:\mathbb Z_n\to\mathbb Z_p\times \mathbb Z_q:x\mapsto(x\bmod p,x\bmod q)$ which will yield $\theta(m)=(0,y)$ for $y:=m\bmod q$. Now, $\theta$ is a ring isomorphism, meaning that it preserves multiplication and addition, that is $\theta(m^e)=(0,z:=y^e\bmod q)$. Because $\theta$ is a bijection, its inverse is unique and the solution $c\in\mathbb Z_n$ to the following set of equations:

\begin{align*}
c&amp;\equiv0\pmod p\\
c&amp;\equiv z\pmod q
\end{align*}
And as you can easily verify, $c=zp$ satisfies these equations, meaning it is the encryption of $m$ and thus a multiple of $p$.