# Why RSA must make sure that $\gcd(e,\varphi(n)) = 1$ instead of $\gcd(e,n) = 1$?

By Euler's theorem, if $$\gcd(e,n) = 1$$, then $$e^{\varphi(n)} \equiv 1 \pmod n$$. But why does RSA need to make sure that $$\gcd(e,\varphi(n)) = 1$$?

You want to be able to encrypt a message and decrypt it, that is translated to:

$$m^{ed} \equiv m^1 \equiv m \pmod n$$

But why does this work? Since $$ed \equiv 1 \pmod{\varphi(n)}$$

If $$\gcd(e,d) \neq 1$$ then $$e$$ and $$d$$ are not coprime then $$ed \not \equiv 1 \pmod{\varphi(n)}$$. So $$e$$ must be coprime with $$\varphi(n)$$ to have a modular multiplicative inverse.

Also $$\gcd(e,n)=1$$, since the public key is presented as $$(e,n)$$. Then you trivially can compute a factor of $$n$$ if $$e$$ is not coprime.

• $ed \equiv 1 \pmod{\varphi(n)}$ is not necessary for $m^{ed} \equiv m^1 \equiv m \pmod n$ to hold for all $m$. Example: $p=5$, $q=11$, $n=55$, $e=3$, $d=7$, $\varphi(n)=40$, $ed\equiv21\not\equiv1\pmod{40}$. Hence the "since" is technically incorrect. – fgrieu Oct 25 at 7:18
• I think that a better argument would be to show that if $\gcd(e,\varphi(n))\ne1$, one can exhibit $m,m'$ with $0\le m<m'<n$ and $m^e\equiv (m')^e\bmod n$, hence reliable decryption would be impossible. – fgrieu Oct 25 at 7:30
• Also: $e$ and $d$ don't have to be coprime. If e.g. x is a square root of $1$ mod $\lambda(n)$, you could also use $e=d=x$. Of course it is quite insecure if it is known you chose it like that. But you still can uniquely decrypt. – tylo Oct 25 at 7:44