# Why $f(x)=x^e$ is a bijection i.f.f $e\in{\mathbf{Z^*_{\phi(N)}}}$?

I understand that if $$e\in{\mathbf{Z^*_{\phi(N)}}}$$ then $$\gcd(e,\phi(N))=1$$ and if $$e\not\in{\mathbf{Z^*_{\phi(N)}}}$$ than $$\gcd(e,\phi(N))\neq{}1$$.

But I couldn't figure out why this implies bijection of $$f(x)=x^e$$.

I also tried to see examples but that didn't help me to explain the phenomenon.

• Could you also post your failed examples? Also, a dupe question Proving RSA is a permutation. – kelalaka Jun 16 '20 at 8:55
• Note that, learning from your errors (LWE) is more valuable for development. That is why I've asked your failed ways. – kelalaka Jun 16 '20 at 9:28
• Actually, it's not true. Counterexample, $\mathbf{N}=8$, $e=3$... – poncho Jun 16 '20 at 10:22
• @poncho The OP tagged RSA. $8$ doesn't form RSA or multi-prime RSA. – kelalaka Jun 16 '20 at 10:35
• If the linked answer satisfies you we can close this question and before that make sure that $N$ is RSA modulus. If you are not talking only RSA then poncho's hint also valid for you. – kelalaka Jun 16 '20 at 13:09

The correct form is: The integer $$a \mod Z_n$$ has multiplicative inverse iff $$gcd(n,a)=1$$
Here, you are working on exponents, so you must consider the modulo as $$\phi(n)$$ not $$n$$.
Therefore, here you can find the inverse of $$e$$ iff $$gcd(e, \phi(e))=1$$. This guarantees that you be able to find the inverse of $$e$$ using extended Euclidean algorithm.