How many Fermat tests are needed to verify a Carmichael number

Question

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

Answer 1

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.

Answer 2

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.