# What is the probability of $\gcd(e,\varphi(n))=1$, where $e$ is an odd number and $\varphi(n)$ is an even number with $e<\varphi(n)$?

This is needed because I use a random function to generate the encryption key in RSA setting to generate random numbers and check if $$\gcd$$ is $$1$$.

• Are you asking that probability for uniformly random $e$ and fixed $n$? If so, that probability can be computed from the list of distinct odd primes factors in the factorization of $\varphi(n)$. Use that the probability of a large random $e$ being divisible by prime $r$ is $1/r$. On the other hand, If $n$ is not fixed, or if the factorization of $\varphi(n)$ is not known, then you need some model of the distribution of $n$ or $\varphi(n)$. Notice that practice in modern RSA is to first chose $e$, then generate the factors of $n$ such that $\gcd(e,\varphi(n))=1$. – fgrieu Jan 30 at 10:40