Theorem 12.3.2. The Square Root of Fermat’s Little Theorem.
\begin{equation*}
\text{For any odd prime modulus }p\nmid a\text{, we have }a^{(p-1)/2}\equiv \pm 1\text{ (mod }p)\text{.}
\end{equation*}
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.
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?
Proof.
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.
Algorithm 12.3.3. Miller’s test for base \(a\).
We will proceed by repeatedly dividing and then checking a congruence.
- Begin with \(n-1\text{;}\) divide it by two, and then check the power\begin{equation*} a^{(n-1)/2}\text{ (mod }n)\text{.} \end{equation*}If the result is \(-1\) we say \(n\) passes Miller’s test. If the result is not \(\pm 1\text{,}\) we say it fails Miller’s test (since if \(n\) is prime, the result would certainly be \(\pm 1\)). If the result is \(+1\text{,}\) we continue.
- If we have arrived at a point where we can no longer divide \(n-1\) by two, we say \(n\) passes Miller’s test. Otherwise, assuming \(a^{(n-1)/2}\equiv 1\text{,}\) we continue by dividing the power itself by two and then taking \(a\) to that new power. Once again, if the result is \(-1\) we say \(n\) passes the test, and if it is not \(\pm 1\text{,}\) we say it fails.
- If the result is \(+1\) and we can continue dividing the power by two, do so and check the result, as often as need be. If we arrive at the point where we have divided \(n-1\) by all possible powers of two and the result is still \(\pm 1\text{,}\) then we say \(n\) passes the test.
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!)
www.math.dartmouth.edu/~carlp/PDF/paper95.pdf
