# For large prime P, how often is (P-1) evenly divisible by 65537?

When calculating prime numbers $p$ and $q$ for an RSA private key, one of the requirements is that $\gcd(p-1,e)=1$ and $\gcd(q-1,e)=1$, where $e$ is the RSA exponent (typically 65537).

I'm curious how often it happens in practice that a randomly generated prime number happens to not satisfy $\gcd(p-1,65537)=1$. Are the chances of this happening related to the size of the prime number?

If you generate a prime randomly, and then check, it happens with probability $1/65536$.
On the other hand, it is common practice to include the criteria $p \not\equiv 1 \pmod {65537}$ as part of the prime search; if you do that, the probability is 0.
• @yyyyyyy: that's because if $p$ is a prime other than $65537$, then $65537$ does not divide $p$, hence $p-1\bmod65537\ne65536$. Rather, for random $p$, the integer $p-1\bmod65537$ is equidistributed on $[0,1,\dots,65534,65535]$ (under some hypothesis cousin to Riemann's, generally believed to hold at least for cryptographic purposes). Primes used in RSA are often with $p\bmod4=3$ because that simplifies the primality test, but everything still applies if we restrict to these primes. – fgrieu Sep 8 '17 at 9:48