# How many bases do you need to check to know that a number is a Carmichael number?

Suppose that $N$ is a Carmichael number, but we don't know that yet and we perform the Fermat test on it: that is for numbers $a$ such that $gcd(a,N) = 1$ we check if $a^{N-1} \equiv 1 \pmod N$.

Since $N$ is Carmichael, it will pass this test for all such $a$, but how many values of $a$ do you need to test before you can be certain that a number is a Carmichael number?

Is $\sqrt{N}$ sufficient? I know that all Carmichael numbers are odd and so if $N$ passes the test to base $a$ is will also pass for base $N-a$, but is there a better bound than just $\frac{N-1}{2}$?

• Well, if $N$ is prime then it will pass all the tests as well. – lulu Apr 16 '18 at 16:20
• You can't be sure with Fermat tests. Use something like math.stackexchange.com/a/1729144/61216 to check for probable Carmichael numbers. – gammatester Apr 16 '18 at 17:14

• If you find a base such that $N$ is a Fermat-pseudoprime but not a strong Fermat-pseudoprime, then you can efficiently find a non-trivial factor of $N$

• Doing $\sqrt{N}$ tests is nonsense. You could as well apply trial division to completely factor the number. Since you assume the number $N$ is a Carmichael number, it must have a factor not exceeding $N^{1/3}$ , but for large $N$ it would still take too long to apply trial division.

• Unfortunately, there is no general bound for a witness ( a base showing that $N$ is composite) because for every finite collection of bases there are infinite many composite numbers passing all those bases.

• You will have to find the factorization to show that $N$ is a Carmichael-number. In this case, there is a nice criterion : If $N$ is composite, odd and squarefree, then $N$ is a Carmichael-number if and only if $p-1|N-1$ holds for every prime $p$ dividing $N$.

• That last point is Korselt's criterion. – J.G. Apr 17 '18 at 6:22
• To the proposer: A Carmichael number will have at least 3 prime divisors. The last part of the "nice criterion" will automatically fail if N has exactly 2 prime divisors. – DanielWainfleet Apr 17 '18 at 11:22
• Peter is correct that in general we have to factor. There are some simple pre-tests to help with arbitrary inputs, such as must-be-odd and an optimistic square-free check (e.g. is it divisible by 9, 25, 49, 121, or 169 -- if so, not Carmichael). Then check Korselt's for small primes (basically a tiny bit of trial division and check as we find the small factors). For large enough input it is often worth a single Fermat test just to toss out some more before factoring. – DanaJ Apr 17 '18 at 17:52

Adding to @Peter's answer it might be instructive to see this a bit better. I've made a program to show the fermat-tests for consecutive bases (row-by-row) and consecutive or selected modules (col-by-col). Here is a screenshot of a short part of the spreadsheet. Where the entry is "1" the pseudoprime N is not detected by base B and conversely.
For $N=1729$ for instance you need to test up to base $B=7$ while for $N=341$ it suffices to test to base $b=3$. I tried one time to find an "optimal set of bases" as small as possible but as detecting as many pseudo-primes as possible. Long time ago I had found even some article on this problem but do not at the moment remember the source...

You can download that program at my webspace (no big thing, just a bit to play with and programmed with Delphi 1.0 or 4.0 about 20 years ago)