RSA Decryption Correctness

Since $ed \equiv 1 \pmod{\phi(n)}$, by definition of modular congruence there is a non-negative integer $k$ with $ed = 1 + k\phi(n)$.

Case 1: $\gcd(m,n)=1$. Euler's theorem gives $m^{\phi(n)} \equiv 1 \pmod n$, so raising both sides to the power $k$ and multiplying by $m$ gives $m^{ed} = m \cdot (m^{\phi(n)})^{k} \equiv m \cdot 1^{k} \equiv m \pmod n$.

Case 2: $\gcd(m,n) \ne 1$. Since $n = pq$, this means $p$ divides $m$ or $q$ divides $m$ (not both, since $m$ is smaller than $n$). Working modulo $p$: if $p$ divides $m$ then both $m$ and $m^{ed}$ are congruent to $0$ modulo $p$; otherwise $\gcd(m,p)=1$ and Fermat's little theorem gives $m^{p-1} \equiv 1 \pmod p$, and since $(p-1)$ divides $\phi(n)$ the same computation as Case 1 shows $m^{ed} \equiv m \pmod p$. The identical argument modulo $q$ shows $m^{ed} \equiv m \pmod q$.

By the Chinese Remainder Theorem, a congruence that holds modulo $p$ and modulo $q$ separately also holds modulo their product $n=pq$, so $(m^e)^d \equiv m \pmod n$ holds for every message $m$, not just those coprime to $n$.