As we all known $c = m^e (mod\ n)$, so $m \equiv c^d (mod\ n) \equiv m^{ed} (mod\ n) \equiv m(mod\ φ(n)) \equiv m^{kφ(n)+1}(mod\ n)$,so we only need to prove that $m \equiv m^{kφ(n)+1}(mod\ n)$

Divided into two situations:

1. $m$ and $n$ are mutually prime

By Euler's theorem $m^{φ(n)} \equiv 1 (mod\ n)$ ,so

$m^{kφ(n)} \equiv 1^k (mod\ n)$

$m^{kφ(n)} \equiv 1 (mod\ n)$

$m^{kφ(n)+1} \equiv m (mod\ n)$

1. $m$ and $n$ are not mutually prime

Let $m < n$, $p$ and $q$ are both prime numbers, which means $m$ is either a multiple of $p$ or a multiple of $q$, and can't be a multiple of both $p$ and $q$ (if it is a multiple of both $p$ and $q$ , then let $m > n$), let $m$ be a multiple of $p$, then $m = cp$, where $c$ is positive, then $gcd(m, q) = 1$, according to Euler's theorem:

$m^{φ(q)} \equiv 1 (mod\ q)$

So

$m^{kφ(q)} \equiv 1 (mod\ q)$

$(m^{kφ(q)})^{φ(p)} \equiv 1^{φ(p)} (mod\ q)$

$(m^{kφ(q)})^{φ(p)} \equiv 1 (mod\ q)$

$m^{kφ(n)} \equiv 1 (mod\ q)$

Therefore, there exists an integer $r$ such that $m^{kφ(n)} = 1 + rq$, multiply both sides by $m = cp$, we can get:

$m^{kφ(n)+1} = m + rcpq = m + rcn$

The result is :

$m^{kφ(n)+1} \equiv m (mod\ n)$

In summary, regardless of whether m and n are mutually prime, RSA can correctly decrypt the message