Pseudo Primes and Carmichael Numbers

In theory, Wilson’s Theorem solves the primality-testing problem.However, the difficulty of computing factorials makes it a very inefficient test, even for fairly small integers. In many cases we can do better by using Fermat's little Theorem, or rather its contra positive, which asserts that if there is an integer $a$ satisfying $a^n \not \equiv a \pmod {n}$, then $n$ is composite. This test is much easier to apply, since in modular arithmetic, large powers can be calculated much more easily than factorials. This is particularly true if a computer, or even a calculator, is available. Although we will restrict attention to examples which are small enough to deal with by hand, it is a good exercise to write programs to extend the techniques to much larger integers.

The method is as follows. If we are given an integer $n$ to test for primality, we choose an integer $a$ and compute $a^n \pmod {n}$, reducing the numbers $mod (n)$ whenever possible to simplify the calculations. Let us say that $n$ passes the base $a$ test if $a^n \equiv a \pmod{n}$, and fails the test if $a^n \not \equiv  a \pmod {n}$; thus if $n$ fails the test for any $a$ then it implies that $n$ must be composite, whereas if $n$ passes the test then it might be prime or composite. For computational simplicity, it is sensible to start with $a = 2$ (clearly $a = 1$ is useless). If we find that $2^n \not \equiv 2 \pmod {n}$, then $n$ has failed the base 2 test and must therefore be composite, so we can stop. 

For instance, $2^6 \equiv 64 \not \equiv 2 \pmod {6}$, so 6 fails the test and is therefore composite. The Chinese knew this test, and they conjectured 25 centuries ago that the converse was also true, that if $n$ passes the base 2 test then $n$ is prime. This turns out to be false, but it took until 1819 for a counterexample to be discovered: there are composite integers $n$ satisfying $2^n \equiv 2 \pmod {n}$, so they pass the base 2 test and yet they are not prime. We call such integers pseudoprimes: they look as if they are prime numbers, but they are in fact composite.

Example:Let's apply the base 2 test to the integer $n=341$

Computing $2^{341} \pmod {341}$ is greatly simplified by noting that $2^{10} = 1024 \equiv 1 \pmod {341}$, so 

$$2^{341} = (2^{10})^{34}.2 \equiv 2 \pmod {341}$$

and 341 has passed the test. However $341 = 11 \times 31$, so it is not a prime but a pseudo-prime. (In fact, knowing this factorisation in advance, one could ‘cheat’ in the base 2 test to avoid large computations: since 11 and 31 are primes, $2^{10} \equiv 1 \pmod {11}$ and $2^{30} \equiv 1 \pmod {31}$, which easily imply that $2^{341}- 2$ is divisible by both 11 and 31, and hence by 341.) By checking that all composite numbers $n < 341$ fail the base 2 test, one can show that 341 is the smallest pseudo-prime.

Fortunately, pseudo-primes are quite rare, but nevertheless, there are infinitely many of them.

Mersenne Numbers $M_p=2^p-1$( $p$ prime) and Fermat Numbers $F_n=2^{2^n}+1(n \ge 0)$ all pass the base 2 test.

Let us return to our primality-testing method. If $n$ fails the base 2 test then we can stop, knowing that $n$ is composite; however, if $n$ passes then it could be prime or pseudo-prime, and we do not know which. We therefore repeat the test. with a different value of $a$. As with $a = 2$, failing the test shows that $n$ is composite, whereas passing tells us nothing. 

In general, we test $n$ repeatedly, each time using a different value of $a$. Note that if $n$ has passed the tests for bases $a$ and $b$ (possibly equal), so that $a^n \equiv  a \pmod{n}$ and $b^n \equiv b \pmod{n}$, then $(ab)^{n} \equiv a^n b^n \equiv ab \pmod {n}$, so $n$ must also pass the base $ab$ test; there is therefore no point in applying this test, and it is sensible to restrict the values of $a$ to successive prime numbers. We call $n$ a pseudo-prime to the base $a$ if $n$ is composite and satisfies $a^n \equiv a \pmod {n}$; thus a pseudo-prime to the base 2 is just a pseudo-prime, as defined earlier.

If we consider $341$ it is passed the base 2 test.If we consider 3.Then $3^{341} \not \equiv 3 \pmod{341}$.ie; 341 fails the base 3 test.

Returning to primality testing, if we eventually find a base $a$ test which $n$ fails, then we have proved that $n$ is composite. If, on the other hand, $n$ continues to pass successive tests, then we have proved nothing definite about $n$; however, it can be shown that the probability of $n$ being prime rapidly approaches 1 as it passes more and more independent tests, so after a sufficient number of tests we can assert that $n$ has a very high probability of being prime. 

While this is not definite enough for a rigorous proof of primality, for many practical purposes (such as cryptography) a high level of probability is quite adequate: the chance of $n$ being composite, after passing sufficiently many tests, is significantly smaller than the chance of a machine or human error in computing with $n.$ This is a typical example of a probabilistic algorithm, where we accept a slight degree of uncertainty about the outcome in order to obtain an answer in a reasonable amount of time. By contrast, the primality test based on Wilson’s Theorem gives absolute certainty (if we can ensure accurate computation), at the cost of unreasonable computing time.

It is tempting to conjecture that if $n$ is composite, then it will fail the base $a$ test for some $a$, so the above algorithm will eventually detect this (possibly after a very large number of tests have been passed). Unfortunately, this is not the case: there are composite integers $n$ which pass the base $a$ test for every $a$, so they cannot be detected by this algorithm. These are the Carmichael numbers, composite integers $n$ with the property that $a^n \equiv a \pmod{n}$ for all integers $a$, so they satisfy the conclusion of prime without being prime.

The smallest example of a Carmichael number is $n = 561 = 3.11.17$. This is clearly composite, so to show that it is a Carmichael number we need to show that $a^{561} \equiv a \pmod {561}$ for all integers $a$, and to do this it is sufficient to show that the congruence $a^{561} \equiv a$ is satisfied modulo 3,11 and 17 for all $a$.

Carmichael numbers occur much less frequently than primes, and they are quite difficult to construct. In 1912, Carmichael conjectured that there are infinitely many of them, and this was proved in 1992 by Alford, Granville and Pomerance. The proof is difficult, but a crucial step is the following elementary and useful result: