# How many Fermat tests are needed to verify a Carmichael number

If $n$ is a Carmichael number, then for all values $a$ such that $0<a<n$ (and $a \perp n$):

$a^{n-1} \equiv 1 \mod n$

However, is it not necessary to check check all $a$ values because for a given $a$ value, and $j$ such that:

$0<j< n$,

$a^{j(p-1)} \equiv 1 \mod n$,

$(a^j)^{p-1} \equiv 1 \mod n$.

Therefore all values generated by $a^j \mod n$ also pass the test.

We also know that if

$(a)^{p-1} \equiv 1 \mod n$,

$(a')^{p-1} \equiv 1 \mod n$,

$(aa')^{p-1} \equiv 1 \mod n$.

Therefore checking values such that $a$ is prime is only necessary.

My question is what is the smallest value $b$ (generically) such that performing all tests $1 \le a \le b$ guarantees that all values $0 < a < n$ also pass the test (thus verifying that $n$ is a Carmichael Number).

• If you are willing to accept the Generalized Riemann Hypothesis for all Dirichlet $L$-functions then it can be proved that for all odd $n \geq 3$, every proper subgroup of $(\mathbf Z/n\mathbf Z)^\times$ does not contain some unit mod $n$ that is $O(\log n)^2$, and Eric Bach refined this to a precise bound with no underdetermined constants: $\leq 2(\log n)^2$. That is, if GRH is true then any subgroup of $(\mathbf Z/n\mathbf Z)^\times$ containing all units $\leq 2(\log n)^2$ must be all units mod $n$. Thus, if you let [to be contd.] – KCd Jan 10 '15 at 0:52
• $H_n = \{a \in (\mathbf Z/n\mathbf Z)^\times : a^{n-1} \equiv 1 \bmod n\}$, which is a subgroup of $(\mathbf Z/n\mathbf Z)^\times$, then $n$ is a Carmichael number if and only if $a^{n-1} \equiv 1 \bmod n$ for all units $a \bmod n$ with $a \leq 2(\log n)^2$. So in the notation at the end of your question, you could use $b = 2(\log n)^2$ if you assume GRH. The proof of the bound $O((\log n)^2)$ is non-trivial; it relies on the "explicit formula" for Dirichlet $L$-functions. – KCd Jan 10 '15 at 0:53

Actually your definition was slightly off: (now corrected)

If $n$ is a Carmichael number, then for all values $a$ coprime to $n$ such that $0<a<n$:

$a^{n-1} \equiv 1 \mod n$

(However it is true for Carmichael numbers that for all values $a$, $a^{n} \equiv a \mod n$ )

So for sure you could detect - with this test - that a Carmichael number is composite by getting to the first prime factor $p_1 < \sqrt[3] n$ (since Carmichael numbers have at least three distinct prime factors) and you only need to test primes on the way.

There are more efficient ways to detect composite numbers of course, Miller-Rabin as an example that builds on the Fermat concept.

• I'm just curious as to where that boundary comes from, could you elaborate, or provide a reference? Thanks. – Dane Bouchie Jan 10 '15 at 0:25
• Carmichael numbers are the product of at least three distinct primes. – Joffan Jan 10 '15 at 0:27

The intent of the question is : If $a^{N-1}\equiv1\ (\ mod\ N\ )$ is satisfied for the bases $a=2,...,b$ , where $b$ is some fixed upper bound, can we be sure that $N$ is a Carmichael-number ?

The answer is no because $N$ could be a prime number. But even if we rule out this case, there are still numbers $N$ with exactly two prime factors, being strong probable prime to the bases $2,...,b$, no matter how large $b$ is. And strong probable prime to bases $2,...,b$ implies that they pass the Fermat-test for the bases $2,...,b$.$N$ cannot be a Carmichael-number, if it has exactly two prime-factors, so the Fermat-test cannot guarantee that a number is a Carmichael-number.

I do not know, if a number $N$ with unknown factorization can be proven to be a Carmichael-number (I think it is impossible). But a single base $a$ coprime to $N$ with $a^{N-1}\ne 1\ (\ mod\ N\ )$ is enough to show that $N$ is not a Carmichael-number.

If $N$ passes the Fermat-test for base $a$, but is NOT strong probable prime to base $a$, then a non-trivial factor of $N$ can be found efficiently. In this case, it might be possible to factor $N$ and use the criterion $p-1|N-1$ for every prime factor $p$ of $N$, which shows that $N$ is a Carmichael number, provided that $N$ is odd and squarefree.