Generating false positives to the Rabin-Miller primality test

Question

For what composite numbers $x$ will $a^{x-1} \equiv 1 \pmod x$ for $a \in [2,n]$?

Can we generate $x$s that give false positives to the Rabin-Miller test for the first, say 10, consecutive integers $a > 1$?

Answer 1

Edited to add: This is actually two different questions, as DanaJ points out in a comment. The Rabin-Miller test is more stringent than simply requiring that $a^{x-1}\equiv 1$ (mod $x$).

Original answer: Yes we can! Any Carmichael number whose smallest prime factor is $\ge 13$ wil do. For instance, $294409 = 37 \times 73 \times 109$, which gives false positives for all $a < 37$. I think the smallest such Carmichael number is $29341 = 13 \times 37 \times 61$, which I found in this paper by G.J.O. Jameson. See the Wikipedia article on Carmichael numbers for more information.

Answer 2

$230004476882957071 = 234271*546631*1796071$ is a base ${2,3,5,7}$ strong pseudoprime (thus all bases $1-10$).

There is one other counterexample here, but they are not easy to construct (as DanaJ pointed out). Let me explain how I constructed the one above:

For any odd prime $p$, by Fermat's Little Theorem, we have

$a^{p-1}=1\pmod p$.

By the law of quadratic reciprocity,

$a^{(p-1)/2}= $$\left( \frac{a}{p}\right)$$ \pmod p$ where $\left( \frac{a}{p}\right)$ is the Legendre Symbol.

If $p=3\pmod 4$, then the Miller-Rabin test is equivalent to a Euler-probable prime test (the identity above) since $(p-1)/2$ is odd.

In general, if $n=3\pmod 4$ and $a^{(n-1)/2}= $$\left( \frac{a}{n}\right)$$ \pmod n$, then for each prime $p | n$, $$\left( \frac{a}{p}\right) = \left( \frac{a}{n}\right)$$

A Miller Rabin counterexample would require that many of these congruences hold, in addition to $n$ being a Carmichael number or pseudoprime to many bases.

Lastly, I would like to point out that counterexamples exist with $n=1\pmod 4$, but they are much harder to construct. Suppose $n=5\pmod 8$. There are two cases to consider. Like with $n=3 \pmod 4$:

$a^{(n-1)/2}= $$\left( \frac{a}{n}\right)$$ \pmod n$

If $\left( \frac{a}{n}\right) = -1$, then for each prime $p | n$, $p=1\pmod 4$, $\left( \frac{a}{p}\right) = -1$ if $p=5\pmod 8$ and $\left( \frac{a}{p}\right) = 1$ if $p=1\pmod 8$.

If $\left( \frac{a}{n}\right) = 1$, then $a^{(n-1)/4}= ±1 \pmod n$. One can check if it is $1$ or $-1$ using quartic reciprocity, and the same conditions as if $n=3\pmod 4$ also hold here.

More complex properties hold for $n=9\pmod {16}$, and when $n-1$ has more factors of $2$, we eventually can prove $n$ is prime (this explains why counterexamples are easier to construct if $n=3\pmod 4$). If $n=2^sd+1$ with $d < 2^s$, and $a^{(n-1)/2}= -1 \pmod n$, then $n$ is prime (Proth's Theorem).