1
$\begingroup$

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.

$\endgroup$
5
  • 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 20:00

1 Answer 1

Reset to default
1
$\begingroup$

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)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .