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.