# 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.

• To whoever 'corrected' this, the probability really is 1/65536, not 1/65537 – poncho Sep 7 '17 at 21:40
• @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
• @fgrieu: actually, that it's equidistributed has been proven by de la Vallée-Poussin; no unproven hypothesis needed... – poncho Sep 8 '17 at 9:59
• Often I wish I had really studied math, rather than math-for-the-electronics-and-computer-science-engineer; and had more than a skin-deep understanding of number theory. – fgrieu Sep 8 '17 at 10:12
• @poncho Sorry, my bad. I seem to have forgotten for a moment that primes are almost never divisible by 65537... – yyyyyyy Sep 9 '17 at 14:52