# RSA: Why must e be relative prime to phi(n) [duplicate]

I've got a question concerning fields used in RSA.

Let's use the following symbols for my example:

{p,q} = primes
{e,n} = public key
{d,n] = private key

I learnt that an inverse element exists if a is coprime to m.

Applied to RSA I would have guessed that e needs to be coprime to n in order to find it's inverse element, because n is used as mod. But according to the rules of RSA it has to be coprime to ϕ(n) (gcd(ϕ(n),e)=1). Why?

• Because $d$ needs to be an inverse of $e$ modulo $\varphi(n)$. Apr 24, 2015 at 19:40

Because RSA takes advantage of the fact that:

$a^{\phi(n)} \equiv 1 \mod n$

Which means:

$a^{\phi(n)+1} \equiv a \mod n$

So, in order to encrypt and decrypt using $e$ and $d$, we need:

$ed \equiv 1 \mod \phi(n)$

Which can only be true if $gcd(e,\phi(n)) = gcd(d,\phi(n)) = 1$