# In RSA encryption, why does the public exponent (usually, 'e') have to be coprime with $\varphi(n)$?

I have seen that there is a similar question here but none that really answers the question. I understand that if I choose the encryption exponent $$e$$ not coprime with $$\varphi(n)$$ then there is not a unique way to decrypt a message.

What I am wondering is what is the mathematical reason behind this? It seems to me that since $$m^{(k \varphi(n)+1)} = m \bmod N$$ and $$d$$ is defined as $$(k\varphi(n)+1)/e$$ then $$d\cdot e$$ is always going to be $$k\varphi(n) +1$$. What am I missing?

Textbook RSA encryption goes $$c\gets m^e\bmod n$$ with $$n=p\,q$$, and $$p$$ and $$q$$ primes (all quantities non-negative integers throughout). The question states

$$d$$ is defined as $$(k\,\varphi(n)+1)/e$$

Yes¹, for some integer $$k$$ such that this division yields an integer. And that can only be the case if $$\gcd(e,\varphi(n))=1$$. Proof: Let $$r=\gcd(e,\varphi(n))$$. This $$r$$ divides $$e$$ and $$\varphi(n)$$. Let $$f=e/r$$, and $$z=\varphi(n)/e$$, both integers. We have $$d=(k\,\varphi(n)+1)/e$$, thus $$e\,d=k\,\varphi(n)+1$$, thus $$r\,f\,d-k\,r\,z=1$$, thus $$r\,(f\,d-r\,z)=1$$. When the product of two integers is $$1$$, both are $$\pm1$$; thus $$r=1$$. Thus by construction of $$r$$, we must have $$\gcd(e,\varphi(n))=1$$.

The definition of $$d$$ in the question implies $$\gcd(e,\varphi(n))=1$$. But the question also asks:

If I choose the encryption exponent $$e$$ not coprime with $$\varphi(n)$$ then there is not a unique way to decrypt a message. What (..) is the mathematical reason behind this?

That's asking for a seldom given proof of: if a decryption of textbook RSA encryption can be consistently made, then $$\gcd(e,\varphi(n))=1$$ must hold. Here we go.

We want RSA decryption to be uniquely possible, the encryption transformation $$m\mapsto m^e\bmod n$$ must thus be injective over $$[0,n)$$, which we assume in the following. This implies three facts:

1. $$e\ne0$$. Proof: otherwise, all messages $$m$$ in $$[1,n)$$ would encrypt to $$c=1$$. There are more than one such $$m$$, contradicting injectivity.
2. $$p\ne q$$ or $$e<2$$. Proof: if otherwise, that is if $$p=q$$ and $$e\ge2$$, then all $$m$$ multiple of $$p$$ encrypt to $$0$$, since for all $$i$$ it holds $$(i\,p)^e=i^e\,p^{e-2}\,p^2$$, hence $$(i\,p)^e$$ is a multiple of $$p^2$$, hence $$(i\,p)^e\bmod n=0$$. There are more than one such $$m$$, contradicting injectivity.
3. $$\gcd(e,\varphi(n))=1$$, which the question asks to prove.

If $$e=1$$, then $$\gcd(e,\varphi(n))=1$$ holds. Given fact (1.), we can restrict the proof of (3.) to $$e\ge2$$, and we do so in the following.

Given fact (2.), $$\varphi(n)=(p-1)(q-1)$$. Thus \begin{align} \gcd(e,\varphi(n))=1&\iff\gcd(e,(p-1)(q-1))=1\\ &\iff\gcd(e,p-1)=1\text{ and }\gcd(e,q-1)=1 \end{align} Thus for the proof of (3.) it is enough that we prove $$\gcd(e,p-1)=1$$ (the same proof applies for $$q$$, giving the desired result). We do so in the following.

Given that $$p$$ is prime, the multiplicative group $$\Bbb Z_p^*$$ (that is the integers $$[1,p)$$ under multiplication modulo $$p$$) has $$p-1$$ elements. It is known to be a cyclic group, thus there exists a generator $$g$$ with $$x\mapsto g^x\bmod p$$ a bijection on $$[1,p)$$, with $$p-1\mapsto 1$$.

Let $$r=\gcd(e,p-1)$$. This $$r$$ divides $$e$$ and $$p-1$$. Let $$f=e/r$$, $$s=(p-1)/r$$, and $$h=g^s\bmod n$$. It holds $$h^e={(g^s)}^e=g^{s\,e}=g^{f\,r\,s}=g^{(p-1)\,f}={(g^{p-1})}^f$$. Hence $$h^e\bmod p=1$$.

Given fact (2.) and $$p$$ and $$q$$ prime, $$p$$ and $$q$$ are coprime. Thus by the Chineese Remainder Theorem there exists² $$t\in[0,p\,q)$$ with $$t\bmod p=h$$ and $$t\bmod q=1$$.

It follows that $$t^e\bmod p=h^e\bmod p=1$$, and $$t^e\bmod q=1^e\bmod q=1$$. Again by the CRT, it follows that $$t^e\bmod n=1$$.

It also holds $$1^e\bmod n=1$$. For RSA encryption $$m\mapsto m^e\bmod n$$ to be injective, we must thus have $$t=1$$, therefore $$h=1$$. Since $$x\mapsto g^x\bmod p$$ is a bijection on $$[1,p)$$, and transforms $$x=p-1$$ into $$1$$, and $$s$$ into $$h=1$$, it must hold $$s=p-1$$.

By construction $$s=(p-1)/r$$ and $$r=\gcd(e,p-1)$$, thus $$\gcd(e,p-1)=1$$, Q.E.D.

Note: for proper generation of $$N$$ the condition $$p=q$$ is extremely improbable, and even if it occurs it leads to vanishingly few $$m$$ which encryption could not be uniquely deciphered, which is why $$p\ne q$$ is sometime omitted in the definition of textbook RSA. However when $$\gcd(e,\varphi(n))\ne1$$, the proportion of $$m$$ which encryption could not be uniquely deciphered becomes sizable, which is why condition (3.) on $$e$$ or an equivalent is always required. An argument for this sizable proportion is that there are many generators $$g$$ leading to distinct $$h$$, and for each $$h$$ that we exhibited there are $$q$$ messages $$t$$ encrypting to the same $$c$$.

¹ A standard proof is that if $$e\,d\equiv 1\pmod{\varphi(n)}$$, then decryption per $$m\gets c^d\bmod n$$ works for most messages in $$[0,m)$$, and for all such messages when $$n$$ is squarefree. The converse does not hold.

² That $$t$$ is unique and could be computed as $$\left((p^{-1}\bmod q)(h-1)\bmod q\right)\,p+1$$.