Is it necessary to use Fermat's Little Theorem to prove the 'correctness' of the RSA Encryption method?

Question

Given a 'message' $M$, a proof of the 'correctness' of RSA encryption means to show that $(M^e)^d \equiv M \pmod{n}$, where $n=pq$ is a product of primes, and $ed \equiv 1 \pmod{\phi(n)}$, where $\phi$ is Euler's totient function, so that $\phi(n)=(p-1)(q-1)$.

Most sources attribute the correctness of RSA encryption to Euler's theorem (a generalisation of Fermat's little theorem), however the end of the intro of the Wikipedia page claims this is erroneous, since it doesn't apply in the case when $\gcd(M,n) \neq 1$, and that actually it is sufficient and necessary to use the "uniqueness provision of the Chinese Remainder Theorem". However, in every proof I can find on the web and on this site, Fermat's little theorem is used as well as CRT.

So, my question is, is it necessary to use FLT? And is it necessary to use CRT?

If so, is there a proof of this, i.e. that FLT / CRT $\Leftarrow (M^e)^d \equiv M \pmod{n}$ ?

Answer 1

The proposition following «show that» in the question's first paragraph requires $p\ne q$ to become true. Problems are that when $p=q$, the expression $\phi(n)=(p-1)(q-1)$ no longer holds, and even fixing it to $\phi(n)=(p-1)\,p$ does not make the proposition true for quite all $M$ and $e$, when $p\ne2$. For example the proposition fails for $p=q=M=3$, $n=9$, $e=d=5$, for both the correct $\phi(n)=6$ and the incorrect $\phi(n)=4$.

---

This proof of that propostion does without the full Chinese Remainder Theorem. Rather, following a suggestion in comment, it uses the more basic fact that if $p$ and $q$ both divide $Z$ and are coprime (including: are distinct primes), then $p\,q$ divides $Z$.

In a nutshell, this is applied to the quantity $Z\underset{\text{def}}=(M^e)^d-M$, leading to the desired conclusion. To show that $p$ divide that $Z$, we distinguish the easy case $M\equiv0\pmod p$, from the other where that follows from $e\,d \equiv 1 \pmod{\phi(n)}$ rewritten as $\exists k,\ e\,d=k\,(p-1)(q-1)+1$, and Fermat's Little Theorem. We could further integrate one of the proofs of the FLT in the demonstration.

---

In conclusion, we can rigorously prove that RSA works without explicitly using either the FLT or CRT, by using or proving slightly less general statements along the way. I see no reason to thus circumvent the use of FLT, because it is so useful. For CRT, that makes sense.

From a pedagogical perspective, if the audience can't stand the FLT, it's not ready for a proof anyway, and we can as well proceed by affirmation and example. At least, let's try to affirm only true propositions.

---

_{A former version of the question used slightly incorrect notation. It is best as it stands now, with $(M^e)^d \equiv M \pmod{n}$ and $e\,d \equiv 1 \pmod{\phi(n)}$. The opening parenthesis immediately on the left of $\bmod$ is to denote modular equivalence, rather than an operator with restriction of the output range to non-negative integers less than the modulus. That notation is obtained with \pmod in $\LaTeX$. Alternatively, we could write $(M^e)^d\bmod{n}=M$ if we add $0\le M<n$. And we could write $d = e^{-1}\bmod{\phi(n)}$.}