In RSA, what is $P[x \notin \mathbb{Z}_N^*]$
With fgrieu's idea:

If we consider the generator working on a security parameter of $n$ bits (meaning resistance to $\mathcal O(2^n)$ computational effort), then each of the prime $p$ and $q$ must be at least (about) $n$-bit, otherwise trial division would factor the public modulus. Then, $N=p\,q$ with $p$ and $q$ distinct primes at least $2^n$ implies $P[x \notin \mathbb{Z}_N^*]=1-\frac{(p-1)(q-1)}{p\,q}&lt;\frac1p+\frac1q&lt;\frac2{2^n}$, that is $\mathcal O(2^{-n})$ which is negligible.