RSA: Given two very large prime $p,q$ and $n=p\;q$, how to quickly find $e$ such that $\gcd(\varphi(n),e)=1$?
Normall practice is to pick public exponent as a small prime(preferably with few set bits in binary representstion). If the public exponent is prime we only need to verify it doesn't devide $\phi(n)$.