True or false: "Any prime number can be used as the public exponent e in RSA."

False — even prime numbers must satisfy $\gcd(e, \varphi(N)) = 1$. A prime $e$ that divides $(p-1)$ or $(q-1)$ is NOT valid.

The rule: $e$ must be coprime with $\varphi(N) = (p-1)(q-1)$.

Example where a prime fails:

• $p = 7, q = 11 \Rightarrow \varphi(N) = 6 \times 10 = 60$
• $e = 5$ is prime, but $\gcd(5, 60) = 5 \neq 1$ → invalid! (because $5 | (q-1) = 10$)
• $e = 3$ is prime, but $\gcd(3, 60) = 3 \neq 1$ → invalid! (because $3 | (p-1) = 6$)
• $e = 7$ is prime, and $\gcd(7, 60) = 1$ → valid ✓

Also note: $e$ doesn't even need to be prime at all!

• $e = 9$ with $\varphi(N) = 20$: $\gcd(9, 20) = 1$ → valid, even though $9 = 3^2$ is composite
• The only requirement is coprimality with $\varphi(N)$

Why $e = 65537 = 2^{16} + 1$ works almost always:

• It's prime, so $\gcd(65537, \varphi(N)) \neq 1$ only if $65537 | (p-1)$ or $65537 | (q-1)$
• For random 1536-bit primes, the probability of this happening is astronomically small
• This is why 65537 is the de facto standard — it almost never conflicts

Go deeper:

• Euler's totient function (Wikipedia) — the $\varphi(N)$ that $e$ must be coprime to (prime or not).
• Fermat number (Wikipedia) — why the prime $65537$ almost never conflicts.