Skip to main content
Logo image

Section 12.3 Another Primality Test

For a long time it was open whether we might be lucky and show there are only finitely many Carmichael numbers. However, as was proved in the mid-nineties 13 , there are infinitely many Carmichael numbers.
So now what? Can we find other ways to reliably get primes?

Subsection 12.3.1 Another pattern

To answer this, we turn to another result visible in our modular power graphic.
Colored table of powers modulo \(n=11\)
Figure 12.3.1. Colored table of powers modulo \(n=11\)
As usual, Fermat’s Little Theorem is the right-hand column. What’s that pattern in the middle column? Can you confirm it in the interactive version?
Since \(a^{p-1}\equiv 1\) we know that \(a^{(p-1)/2}\) is a solution to \(x^2\equiv 1\text{.}\) (Note that \(p\) is odd so \((p-1)/2\) makes sense.)
As in Section 7.3, we can rewrite and factor the congruence \(x^2\equiv 1\) as \(p\mid x^2-1=(x+1)(x-1)\text{.}\) Given that \(p\) is an odd prime, that means \(p\mid x-1\) or \(p\mid x+1\text{.}\)
Then \(x\equiv \pm 1\) (mod \(p)\text{.}\) (This is restated in Subsection 16.1.1.) Since \(a^{(p-1)/2}\) is one such solution, then \(a^{(p-1)/2}\equiv \pm 1\) (mod \(p\)).
What is the use for us of this theorem? Think similarly to the pseudoprime situation. Imagine we are testing some number \(n\) for primality, but we then find that
\begin{equation*} a^{(n-1)/2}\not\equiv \pm 1\text{ (mod }n)\text{,} \end{equation*}
then that number is definitely not prime.
Let’s try this on our pesky Carmichael number, once again starting with base \(a=2\text{.}\) (Remember that we already know \(2^{561-1}\equiv 1\) since \(561\) is a pseudoprime.)
Not again! Try another base – maybe \(a=3\text{?}\)
Phew, this works, as \(3^{(561-1)/2}\not\equiv \pm 1\) (and \(561\) is not prime). So this criterion does help us test at least a little better.

Subsection 12.3.2 Miller’s test

A slightly stronger variant of this test is called Miller’s test base \(a\) for primality, after American computer scientist Gary Miller.

Example 12.3.4.

Let’s see a few examples of this. First, the number \(1387\) is a pseudoprime base 2 – but it does not pass Miller’s test, which is good since it’s composite. Try the following cell to see exactly what happens.
Looking good … But let’s try another pseudoprime number (the Mersenne number \(M_{11}\text{,}\) in fact) to see if it passes, just to be sure.
As we can see, this shows that \(n=2047\) passes the first part of Miller’s test base 2, and that there is no further to go because \((2047-1)/2=1023\) is odd. So, as far as we know thus far, \(2047\) is prime (though actually it is the lowest Mersenne number with prime exponent not to be prime).
Let’s try Algorithm 12.3.3 with another number, \(1009\text{.}\)
This passes Miller’s test the first time, but the algorithm keeps going since our first computation was \(\equiv 1\text{.}\) The second time we got \(\equiv -1\text{,}\) so we stop and hope the number is prime. (It is, in this case!)