In the process of creating a Pratt certificate to prove that a number *n* is prime, you have to find a number *a* that seems kinda arbitrary. As we discussed here, a number *n* is prime if there exists a number *a* such that

*a*^{n−1} = 1 mod *n*

and

*a*^{(n−1)/p} ≠ 1 mod *n*

for all primes *p* that divide *n* − 1. How do you find *a*? You try something and see if it works. If it doesn’t, you try again.

How many values of *a* might you have to try? Could this take a long time?

You need to pick 2 ≤ *a* ≤ *n* − 2, and there are φ(*n*−1) values of *a* that will work. Here φ is Euler’s totient function. So the probability of picking a value of *a* that will work is

*p* = φ(*n*−1) / (*n* − 3).

The number of attempts before success has a geometric distribution with parameter *p*, and an expected value of 1/*p*.

So about how big is *p*? There’s a theorem that says that φ(*n*)/*n* is asymptotically bounded below by

exp(−γ) / log log *n*

where γ = 0.577… is the Euler-Mascheroni constant. So for a 50-digit number, for example, we would expect *p* to be somewhere around 0.12, which says we might have to try eight or nine values of *a*. This estimate may be a little pessimistic since we based it on a lower bound for φ.