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.

  • 2
    $\begingroup$ 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$. $\endgroup$ – Dietrich Burde May 9 at 15:12
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Thomas Andrews May 9 at 15:34
  • $\begingroup$ 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}.$ $\endgroup$ – Thomas Andrews May 9 at 15:43
  • $\begingroup$ @ThomasAndrews no proving for values that pass for all a coprime to n, will edit the question to reflect $\endgroup$ – W M Seath May 9 at 19:45
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews May 9 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)$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.