Proof For RSA where $(m,n) \neq 1$ My definition of the RSA algorithm for this question is as follows:
For p and q large primes: $n = p*q$
Then if the receiver $R$ of a message $m$ chooses $a$ s.t. $(\phi(n), a)=1$, the relationship $1=ax + \phi(n)y$ allows $S$ to encrypt a message $m$ as ciphertext $c$, and $R$ to decipher a ciphertext $c$ as follows:
$$c \equiv m^a \pmod n$$
$$m \equiv c^x \pmod n$$
The proof for decryption is as follows:
$$c^x \equiv (m^a)^x \equiv m^{ax} \equiv m^{1-y\phi(n)} \equiv m*(m^{-y})^{\phi(n)}\pmod n$$
If $(m,n)=1$ Euler's Theorem states that $m^{\phi(n)} \equiv 1 \pmod n$. So using this for assumption $(m,n)=1$ we have:
$$m*(m^{-y})^{\phi(n)} \equiv m * 1 \equiv m \pmod n$$
My professor showed in class that this is true even when $(m,n) \neq 1$ using the notion that $p^{\phi(n) + 1} \equiv p \pmod n$ for $p | n$ but $p^2 \nmid n$. Since $n=pq \implies p^2 \nmid n$, the identity proves useful and he proves this like so:
let $m = p$ (or $q$). Then, $c \equiv p^a \pmod n \implies c^x \equiv p^{ax} \mod n$. Using Euclid's Extended GCD algorithm, we substitute $ax=1-y\phi(n)$ to find $p^{ax} \equiv p^{1-\phi(n)y} \equiv p*(p^{\phi(n)})^{-y} \equiv p*p^y*(p^{\phi(n)+1})^{-y} \equiv p * p^y * (p)^{-y} \equiv p \pmod n$. Thus, the RSA algorithm works for $(m,n) \neq 1 \implies m=p$ or $m=q$
When I went to prove this, I proved that $m | c^x \implies c^x \equiv p \pmod n$ as follows:
let $m = p$ (or $q$). Then, $c \equiv p^a \pmod n \implies c^x \equiv p^{ax} \mod n$. Since $n=pq$, $c^x \equiv p^{ax} \equiv p^{1-\phi(n)y} \equiv p * (p^{-y})^{phi(n)} \pmod {pq}$
Given: 
$$c^x \equiv p * (p^{-y})^{\phi(n)} \pmod {pq}$$
$$\phi(n) = \phi(p*q) = k*\phi(q)$$ where k is some integer ($k=p-1$)
If $p|c^x$, then:
$$\frac{c^x}{p} \equiv (p^{-y})^{k\phi(q)} \pmod {q}$$
Since $(p,q)=1$ we have by Euler's Theorem that $\frac{c^x}{p} \equiv 1 \pmod q \implies c^x \equiv p \pmod {pq}$. So only if $p|c^x$ does my proof show that $c^x \equiv p \pmod n$.
Finally, my question, is this an if and only if relationship such that my professor's proof confirms that $m=p$ (or $q$) $\implies$ $p|c^x$, why or why not? Is there a separate proof for $p|c^x$ that would allow me to complete mine? What would be the possible security implications of such a property?
 A: So suppose we have $N = pq$ with $e$ the encryption exponent, chosen such that $\gcd(e,\phi(N)) = 1$ and we have a $d$ and a $k$ in $\mathbb{Z}$ such that
$$ed + k\phi(N) = 1$$ by Bézout's identity and you want to show $d$ is the decryption exponent.
The proof that $m^{ed} = m \bmod {pq}$ for all $m \in \mathbb{Z}_N$ can be a bit simplified, based on two main facts:

(1) Euler's theorem: if $n \ge 2$ is an integer and $\gcd(m,n) = 1$, then $m^{\phi(n)} = 1 \bmod{n}$.
(2) A consequence of the Chinese remainder theorem: Let $p,q$ be distinct primes: if $a=b \bmod{p}$ and $a=b \bmod{q}$ then $a=b \bmod{pq}$ for all integers $a,b$.

The easy case: $\gcd(m,N) = 1$: because then $$m = m^1 = m^{ed + k\phi(N)} = m^{ed}\cdot (m^{\phi(N)})^k = m^{ed} \cdot 1^k = m^{ed} \bmod{N}$$
using (1) to simplify $m^{\phi(N)} \bmod{N}$.
On the other hand, if $\gcd(m,N) \neq 1$ we either have $\gcd(m,N) = p$ or $\gcd(m,N) = q$, I'll do the first case, as the second is similar.
So if $\gcd(m,N) = p$, $m = 0 \bmod{p}$ and so $$m^{ed} = m \bmod{p}\text{.}$$
Modulo $q$ we have (using $\phi(N) = \phi(p)\phi(q)$: $$m = m^{ed + k\phi(p)\phi(q)} = m^{ed}(m^{k\phi(p)})^{\phi(q)}$$ and as $m$ is a multiple of $p$, so is any power of it and hence $\gcd(m^{k(p-1)}, q) = 1$ and we can apply (1) to $q$ and see that $(m^{k\phi(p)})^{\phi(q)} = 1 \bmod{q}$ and so $$m^{ed} = m \bmod{q}\text{.}$$
By (2) we conclude $m = m^{ed} \bmod{pq}$, as required.
All of this has no security implications: if you happen to choose $m$ with $\gcd(m,N) \neq 1$ you have factored $N$ and broken this RSA instance. But $p,q$ are chosen so large that the probability of this happening is very small indeed. It's not a condition that's checked for in software, e.g., as it does not affect correctness. And generating random messages and checking the gcd is not a realistic attack for a 2048 bit modulus.
