If a positive integer $N>1$ is a Carmichael number, it passes the weak Fermat-pseudoprime-test for every base coprime to it.

I wonder whether the converse is true in the following sense :

Is there a finite set of bases $b_1,\cdots ,b_n$ such that every positive integer $N>1$ passing the weak Fermat-pseudoprime-test for all those bases is either prime or a Carmichael number ?

A similar question has a negative answer : There is no finite set of bases $b_1,\cdots ,b_n$ such that a positive integer passing the strong Fermat-pseudoprime-test for all those bases must be prime.

So I would not be too surprised if my question also would have a negative answer.

The following would be sufficient to answer my question in the negative sense : Suppose , $p$ is a prime number such that $q:=2p-1$ is prime as well.

Let $s$ be the smallest positive integer that is a quadratic non-residue modulo $q$. Then, $s$ is also the smallest base satisfying $$s^{pq-1}\ne 1\mod pq$$ and since $pq$ is neither prime nor a Carmichael number, we only have to show that $s$ can be arbitary large.

  • $\begingroup$ For $p=167567760361$ , the smallest non-residue of $q=2p-1$ is $107$ $\endgroup$ – Peter Aug 13 '18 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.