# 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<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.

Fix $m = p \cdot z$ for some $z$. Let $c = m^e \bmod n = p^e \cdot z^e \bmod n$, so that $c \equiv p^e \cdot z^e \pmod n$. This means that there exists some $k$ such that $$c = p^e \cdot z^e + k \cdot n = p^e \cdot z^e + k \cdot p \cdot q.$$ Does $p \mid c$?
Let $m,e,n=pq$ be arbitrary with $\gcd(p,q)=1$. Let's assume $\gcd(m,n)>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&\equiv0\pmod p\\ c&\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$.