# How does Euler's Theorem show that $(m^e)^d ≡ m \bmod n$

In this thread Henrick Hellström says that when $$ed \equiv 1\ (mod\ \phi(n))$$ then $$(m^e)^d \equiv m\ (mod\ n)$$. So I thought this is how Euler's theorem is related to RSA. But at least I thought that due to Euler's theorem the prerequisite for $$(m^e)^d \equiv m\ (mod\ n)$$ was $$ed \equiv 1\ (mod\ \phi(n))$$, until I read the comments of the answer and @poncho says that

Minor nit: it's not true that e,d must meet (satisfy) the equation $$ed \equiv 1\ (mod\ \phi(n))$$. One counterexample is $$n=133, e=5, d=11$$. That has $$ed \equiv 55\ (mod\ \phi(n)=108)$$, however $$(m^e)^d \equiv m\ (mod\ n)$$ for all m. This is a minor point, however we should avoid telling beginners things which aren't true.

So $$ed \equiv 1\ (mod\ \phi(n))$$ doesn't need to be true in order for $$(m^e)^d \equiv m\ (mod\ n)$$ to work. At this point I am really confused about the relation between Euler's theorem and RSA, and why we need $$gcd(e,d)=1$$.

EDIT: Also this website says that $$(m^e)^d \equiv m^{\phi(n)}\ (mod\ n)$$. How could this be true? Wouldn't this imply that $$ed =\phi(n)$$?

• If you don't know what your question is, well, it's really hard to answer. BTW: did you mean $\gcd(e, d) = 1$? That doesn't need to be true, and I can't think of anyone claiming that it is. Did you mean $\gcd(m, n) = 1$ (which also doesn't need to be true, but might be implied if you use Euler's theorem as your proof) – poncho Feb 1 '19 at 21:22
• @poncho Oh poncho thank you for showing up! I just don't understand your comment. You showed that ed≡1 (mod ϕ(n)) doesn't need to be true for (me)d≡mϕ(n) (mod n) to work. I thought that Euler's theorem basically proved that, for (me)d≡mϕ(n) (mod n) to work, ed≡1 (mod ϕ(n)) must be true. If that is not the case: 1. Why does (me)d≡mϕ(n) (mod n) work? 2. How is Euler's theorem related to this? – Uzi Feb 1 '19 at 21:36

## 1 Answer

I thought that Euler's theorem basically proved that, for $$(m^e)^d \equiv m \pmod n$$ to work, $$ed \equiv 1 \pmod {\phi(n)}$$ must be true

No; a direct application of Euler's theorem shows that if $$ed \equiv 1 \pmod {\phi(n)}$$ is true (and $$\gcd(m,n)=1$$, Euler's theorem needs that as well), then we always have $$(m^e)^d \equiv m \pmod n$$

However, it does not imply the converse (and in fact, the converse is not true).

A stronger statement would be (assuming $$n = pq$$ for distinct primes $$p, q$$) that if $$ed \equiv 1 \pmod{ p - 1}$$ and $$ed \equiv 1 \pmod{ q - 1}$$, then we have $$(m^e)^d \equiv m \pmod n$$ for all $$m$$.

And, in this case, the converse is true; if we have $$(m^e)^d \equiv m \pmod n$$ for all $$m$$, then we necessarily have $$ed \equiv 1 \pmod{ p - 1}$$ and $$ed \equiv 1 \pmod{ q - 1}$$. In fact, if we have either $$ed \not\equiv 1 \pmod{ p - 1}$$ or $$ed \not\equiv 1 \pmod{ q - 1}$$, then we'll necessarily have $$(m^e)^d \not\equiv m \pmod n$$ for at least 1/3 of the possible $$m$$ values.

Another (perhaps more common) way of writing these two equivalences is to express it as $$ed \equiv 1 \pmod{ \lambda(n) }$$ for the function $$\lambda(n) = \text{lcm}(p-1, q-1)$$.

How does these stronger statements relate to your original relation? Well, if we have $$ed \equiv 1 \pmod{\phi(n)}$$, then we necessarily have $$ed \equiv 1 \pmod{\lambda(n)}$$ (and hence RSA "works")

• So by setting ed≡1(modϕ(n) and gcd(m,n)=1 as true we are basically guaranteeing that (m^e)^d≡m(mod n) is also true. But these are not the only conditions where (m^e)^d≡m(mod n) is true, but with these conditions it is guaranteed that this is true (hence the decryption will work). Did I understand this correctly? And is your stronger statement utilised in RSA or the first one? Because from what you wrote, I understand that RSA works because if ed≡1(modϕ(n)) is true, then ed≡1(modλ(n)) is true as well? I thought Carmichael's function is just an interchangable function with the totient function – Uzi Feb 2 '19 at 8:31
• "And is your stronger statement utilised in RSA or the first one?"; well, real RSA implementations typically use $d = e^{-1} \bmod{ \lambda(n) }$, and so I believe the answer would be "typically the stronger statement". "I understand that RSA works because if $ed \equiv 1 \pmod{\phi(n)}$, then $ed \equiv 1 \pmod{\lambda(n)}$ as well"; yes, that's why the first formulation guarantees correctness. "I thought Carmichael's function is just an interchangable function with the totient function"; obviously not, as those two functions return different values when passed a composite. – poncho Feb 2 '19 at 14:40
• Sorry to bother you again but I am not sure if I am understanding this correctly. (m^e)^d≡m(mod n) works because ed≡1(modλ(n)) is true? And this works because of Euler's Theorem? – Uzi Feb 2 '19 at 17:11
• @Uzi: while it is true that (for squarefree $n$), $(m^e)^d \equiv m \pmod n$ holds for all $m$ exactly when $ed \equiv 1 \pmod{\lambda(n)}$, however we can't really say "because", as there really isn't any causality in math; one equation being true doesn't really cause other expression to be true; both are true or both are not. Similarly, while we might be able to show this using Euler's theorem (although it would not be straightforward), there really isn't any causality... – poncho Feb 2 '19 at 17:26
• @Uzi: that is correct; however a straight-forward application of Euler's theorem doesn't directly prove that; it shows the weaker relation I originally mentioned. – poncho Feb 2 '19 at 18:03