Fact12.2.1
If there is an \(a\) such that \(a^n\not\equiv a\) (mod \(n\)), then \(n\) must be composite.
Section12.2Primes – Probably¶ permalink
Primality testing is full of little tidbits like in the previous section, and tantalizingly devoid of easy methods that work for all special cases. Indeed, none of these paths lead us to reliable, reasonably fast discovery of large primes for cryptographic purposes, nor do other computationally infeasible methods like using Wilson's Theorem or other even stranger formulas (some of which appear later in the text).
Instead, what is typically done is to pick a number, and then use tests on it that do not guarantee primality!
Why would this work? The idea is that if you use enough tests that do not guarantee primality but have a quite low false positive rate in practice, then the number you have is more likely to be a prime than the chance that your computer made an arithmetic error.
This is astonishing, but true; and if you end up with a number that likely to be prime, you can always check it with one of the various slower tests I will not describe.
Subsection12.2.1Pseudoprimes
We start this discussion with our visual representation of powers (see Subsection 8.2.1).
Notice again here that Fermat's Little Theorem is visible in the second-to-last column. The graphic has been expanded, so that the last column is a slight restatement thereof, true for all \(a\): \begin{equation*}a^p\equiv a\text{ (mod }p)\, .\end{equation*} (See Exercise 12.7.3.)
This is useful, as it works for all input. We can now use it to state a test for possible primality:
So if \(a^n\equiv a\) (mod \(n\)) for a given \(n\), it's at least possible that \(n\) is prime.
Definition12.2.2
If \(a^n\equiv a\) (mod \(n\)), we say \(n\) passes the base \(a\) test.
Definition12.2.3
If \(a^n\equiv a\) (mod \(n\)) but \(n\) is not prime, we say it is a pseudoprime base \(a\).
That is to say, if a number satisfies Fermat's Little Theorem, we think it is likely enough to be prime to call it a pseudoprime.
It turns out that everyone from the ancient Chinese to Leibniz used this test for the base \(a=2\) to assert numbers are prime. And it doesn't do a bad job. As some former students pointed out, it's sort of like internet date matching for primes; it doesn't always work but can succeed reasonably often.
We can change the numbers in the range above to check for more – say up to 1000, which allows exploring the following question.
Question12.2.4
Are there any numbers which satisfy the base \(a\) test and are not prime?
To the surprise of many in the world of numbers, the answer is yes. The numbers \(n=341\), \(n=561\), and \(n=645\) turn out to fall in that category.
That's still not bad – out of 171 total such potential pseudoprimes base 2, only 3 of them actually are not prime, or about one and three quarters percent.
Perhaps unfortunately to cryptographers (though interestingly to pure mathematicians!), it turns out that there are infinitely many such pseudoprimes.
Fact12.2.5
If \(n\) is a pseudoprime (base 2), then so is \(2^n-1\).
We will get this result as a corollary of something stronger soon (see Corollary 12.4.3 and Theorem 12.4.2).
All the Fermat and Mersenne numbers pass the base \(2\) test, incidentally, though they are all quite large compared to a typical number you might try.
Subsection12.2.2Prime impostors, and how to avoid them
If we want to check things out more carefully, we can try to test for primality with a different base. In the next cell, we choose \(a=3\).
As you can see, this exposes 341 and 645 as fakes. What about 561? Let's try that one with base 5 as well.
Hmm, that's interesting. What if I add some primes, like 7 or 11? Try it above.
In the next cell, I get systematic. We should expect output if \(561\) doesn't pass the base \(a\) test for some \(a\).
It appears that \(p^{561}\equiv p\) mod 561 for every prime \(p\)! Let's prove it.
Fact12.2.6
The number \(561\) is a pseudoprime for every prime base \(p\).
Definition12.2.7
We call a number which is pseudoprime to every base \(a\), but is not a prime number a Carmichael number, in honor of the first person to actually produce such numbers, Robert Carmichael (in 1912).
So is \(561\) a Carmichael number? We saw the factorization above, but here it is again:
The proof of Fact 12.2.6 suggests that to find a Carmichael number, we might want to look at \(n\) which are a product of primes \(p_i\) such that \(n-1\equiv 1\) in the exponent world of \(p_i\). It turns out that this is true, and we can prove something even more specific.
Proposition12.2.8Korselt's Theorem
Carmichael numbers are precisely those composite \(n\) for which \(n\) is a product of at least two distinct primes \(p_i\) (no squares) \begin{equation*}n=p_1p_2p_3\cdots p_k\text{ with }p_i\neq p_j\end{equation*} such that \begin{equation*}p_i-1\mid n-1\end{equation*} for all the prime factors.
Example12.2.9
Here is another Carmichael number.