The proof [as it stands now][1] has at least one serious gap: it does not explicitly use that $$(\;p\text{ and }q\text{ are primes}\;)\text{ and }(\;p\ne q\;\text{ or }\;\gcd(m,pq)=1\;)$$ which is a necessary condition in RSA (illustration: try $p=q=m=5$, $e=3$; encryption followed by decryption yields $0$ rather than $5$ ). That gap is in the step where it is said that Fermat's little theorem implies $m^{\phi(pq)}\equiv1\pmod{pq}$, which is a nontrivial consequence of Fermat's little theorem, that holds for $p$ and $q$ distinct primes or with a restriction on $m$. Independently: it is used, but not stated, that the definition of RSA considered uses $d$ such that $ed\equiv1\pmod{\phi(pq)}$. Another popular definition uses $ed\equiv1\pmod{\lambda(pq)}$ , where $\lambda$ is the [Carmichael function][2]. That definition is used in PKCS#1 et FIPS 186-4. It is mathematically satisfying, for it is necessary and sufficient, when $ed\equiv1\pmod{\phi(pq)}$ is merely sufficient. Also: the proof would be be clearer if it restated all assumptions, including the missing - $p$ and $q$ prime; - $p\ne q$, if applicable; - $N=pq$ ; - hypothesis on $m$ (that is $0\le m<N$, further restricted to $\gcd(m,N)=1$ if the condition $p\ne q$ is not used); - use of textbook RSA encryption $m\to c=m^e\bmod N$ ; - use of textbook RSA decryption $c\to m'=c^d\bmod N$ (with a distinct notation for the original message and deciphered messages); - what's to be demonstrated (that is $m'=m$ ). Also: there's a missing bit of reasoning, going from $m'\equiv m\pmod N$ to $m'=m$. Finally: textbook RSA is not a secure encryption algorithm (assume encryption of the name of someone in the public class roll, which will be interrogated tomorrow, and how one can easily determine if that's her/him). [1]: https://crypto.stackexchange.com/revisions/51284/5 [2]: https://en.wikipedia.org/wiki/Carmichael_function