The Probability that a Random Probable Prime is Composite
Su Hee Kim, Carl B. Pomerance · Mathematics of Computation · 1989
Consider a procedure which (1) chooses a random odd number $n \leq x$, (2) chooses a random number b, $1 < b < n - 1$, and (3) accepts n if ${b^{n - 1}} \equiv 1\;\pmod n$. Let $P(x)$ denote the probability that this procedure accepts a composite number. It is known from work of Erdös and the second author that $P(x) \to 0$ as $x \to \infty$. In this paper, explicit inequalities are established for $P(x)$. For example, it is shown that $P({10^{100}}) < 2.77 \times {10^{ - 8}}$ and that $P(x) \leq {(\log x)^{ - 197}}$ for $x \geq {10^{{{10}^5}}}$.