# Probability the Fermat test returns "probably prime"

We aim to show that probability of odd $$n>1$$ passing the Fermat test for all bases a coprime to n is $$\frac{1}{\phi(n)}\prod_{p|n, p \ prime}gcd(p-1,n-1)$$where $$\phi$$ is the Euler totient function. We already know that the only numbers that pass are primes and Carmichael numbers, so satisfy

(i)$$\ n$$ is square-free

(ii)For all $$p|n$$, we have $$\ p-1|n-1$$

The probability that $$d|n$$ is $$1-\frac{1}{n-1}\phi(n-1)$$, but other than this I am unsure as to how to go about proving this. Thanks.

• Heath-Brown proved that the number of Carmichael numbers up to $x$, denoted by $C(x)$, satisfies $C(x)>x^{2/7}$ for sufficiently large $x$. May 9, 2019 at 15:12
• Wait, what test are you applying? Are you picking a single $a$ and computing $a^{n-1}\equiv 1\pmod{n}$? Because that can give a false positive for some $a$ and not make $n$ a Carmichael number - a Carmichael number gives a false positive for all $a$ relatively to $n.$ May 9, 2019 at 15:34
• In particular, there are pairs $(q,a)$ with $q$ prime such that $a^{q-1}\equiv 1\pmod{q^2}$ and so with $n=q^2,$ $a^{n-1}\equiv 1\pmod{n}.$ May 9, 2019 at 15:43
• @ThomasAndrews no proving for values that pass for all a coprime to n, will edit the question to reflect May 9, 2019 at 19:45
• Ah, yeah, that's not really a "test," then, in the usual sense, since it takes at about the same time as checking all primes less than $sqrt{n},$ at least unless you have a fast way to prove that it passes for all $a$ relatively prime to $n$ without $1$ proving directly that $n$ is prime, or proving that it is a Carmichael number. May 9, 2019 at 20:00

We let $$n$$ have factorisation $$n=\prod_{p_i|n} p_i^{\alpha_i}$$ By the Chinese Remainder Theorem, the number of solutions to the congruence $$b^{n-1}=n\mod{n}$$ is the product of the number of solutions to the congruences $$b^{n-1}=1\mod{p_i^{\alpha_i}}$$. For each such $$p_i$$, the multiplicative group modulo $$p_i^{\alpha_i}$$ is cyclic order $$\phi(p_i^{\alpha_i})=p_i^{\alpha_i-1}(p_i-1)$$.
Since $$p_i|n, n-1$$ is prime to $$p_i^{\alpha_i-1}$$, so the number of solutions in the multiplicative group modulo $$p_i^{\alpha_i}$$ is $$gcd(p_i-1,n-1)$$. Dividing by each $$\phi(p_i^{\alpha_i})$$ and taking the product across all $$i$$ we get our result $$\frac{1}{\phi(n)}\prod_{p_i|n}gcd(p_i-1,n-1)$$