RSA private exponent primality I know that the public exponent is always a prime, but what about the private exponent? Is it always a prime too?
Actually, the public exponent doesn't have to be prime; any odd number works just fine there.  The most common public exponents (3, 17, 65537) all happen to be prime, but there's no requirement.

Now, it turns out that a prime public exponent does make RSA key generation slightly easier in this respect; when you select primes $p$ and $q$, we need to make sure that $p-1$ and $q-1$ are both relatively prime to the public exponent $e$.  If the public exponent $e$ happens to be prime, then this is equivalent to saying that $p \ne 1 \pmod e$ and $q \ne 1 \pmod e$; these can be easy tests to fold into the prime search.  If $e$ is composite, then the conditions are slightly more complex -- certainly not impossible to accomplish, to be sure.

That said, the private exponent need not be a prime number.  All the private exponent $d$ is is a number such that $de \equiv 1 \pmod{ \operatorname{lcm}(p-1, q-1) }$; $d$ will always be odd, but there's no specific reason why it can't be (say) a multiple of 3.