A Carmichael number is a composite number $N$, such that $a^{N-1}\equiv 1\mod N$ holds for every $a$ coprime to $N$. $N$ is a Carmichael number if
- $N$ is odd and squarefree
- $N$ has at least three distinct prime factors
- For each prime factor $p|N$ we have $p-1|N-1$
A positive integer $M$ is given.
How can I efficiently find the smallest Carmichael number $N\ge M$ ?
For example, the smallest Carmichael-number above $10^{10}$ is $$10017089857=73\cdot163\cdot577\cdot1459$$
I am looking for a method more efficient than brute force, something like a Carmichael-sieve. Any ideas ?
I don't believe that there is a much better way to efficiently find a specific Carmichael number. Actually, the computations done at OEIS by Pinch list all Carmichael numbers up to $1713045574801$. So $10^{10}$ is not a problem.
On the other hand one can find an easy upper bound for the smallest Carmichael number above $10^{10}$ by using Chernick's criterion: if $k$ is a positive integer such that $6k + 1, 12k + 1$, and $18k + 1$ are all prime then the product $$ n = (6k + 1)(12k + 1)(18k + 1) $$ is a Carmichael number. For $k=195$ the criterion applies, because $6\cdot 195+1$, $12\cdot 195+1$, and $18\cdot 195+1$ are all prime, so that $f(195)=9624742921$ is a lower bound for the largest Carmichael number below $10^{10}$ (which is $9999109081$). For a Carmichael number above $10^{10}$ we can take $k=206$, so that $11346205609$ is a Carmichael number above $10^{10}$. Of course, this will not be enough to efficiently find a specific Carmichael number as said.