Posted by Jason Polak on 26. November 2017 · Write a comment · Categories: number-theory · Tags: ,

Since the days of antiquity, we’ve always been looking for ways to determine whether a natural number is prime. Trial division up to the square root of a number quickly becomes tedious, thought it is worth noting that even on my fairly old laptop a slightly optimised trial-division algorithm will list all the primes under 10^7 in just under seven seconds.

Another method that sometimes works is Fermat’s little theorem:

Theorem. If $n$ is a prime number then for every $a$,
$$a^n\equiv_n a.$$

Here, I’m using the notation to mean $a^n – n$ is divisible by $n$. Let’s do some examples: 4^11 – 4 = 4194300, which is divisible by 11 (you can see this directly by using the alternating sum digit test: 4 – 1 + 9 – 4 + 3 = 11). On the other hand, $2^{69} – 2 = 590295810358705651710 \equiv_{69} 6$. Of course, from the nature of the theorem, if $a^n\equiv_n a$ is not true then $n$ is composite, so it can tell you for sure if a number is composite but not if a number is prime.

Crucial in this theorem is that you have to pick $a$ carefully. Obviously $a=1$ is no good because $1^n – 1 = 0$ for all $n$. However, other numbers might not be good either. For example, even though 111 is a composite number, it divides $a^{11} – a$ for $a = 36, 37, 38, 73, 74, 75, 110$. If $n$ is a composite number such that there exists an $a$ with $a^n \equiv_n a$ then we say that $n$ is a Fermat pseudoprime to the base $a$. These are numbers that satisfy the conclusion of Fermat’s little theorem for some $a$. In fact, for each base $a$ it can be shown that there are infinitely many composite numbers $n$ such that $a^n\equiv_n a$.

But surely these fake primes won’t satisfy the congruence $a^n\equiv_n a$ for every $a$ right? Wrong. It gets worse. There are some composite numbers that are really good at being pseudoprimes, because they are pseudoprimes to every base. Here is what they are called:

Definition. A composite number $n$ is called a Carmichael number if $a^n\equiv_n a$ for every $a$.

What are some Carmichael numbers? The first three are 561, 1105, 1729. To find them, you could just check by hand whether $a^n \equiv_n a$ for every $a \in $\Z/n$. However, a better way do find them is use Korselt’s criterion:

Theorem. A composite natural number $n$ is a Carmichael number if and only if $n$ is squarefree and $p – 1 \mid n-1$ for each prime factor $p$ of $n$.

This theorem is extremely convenient, because it characterises Carmichael numbers and, if you have access to some good algorithms for factoring, you can compute some Carmichael numbers much more quickly than with the naive method. Here are all the Carmichael numbers under $10^5$:

  1. 561
  2. 1105
  3. 1729
  4. 2465
  5. 2821
  6. 6601
  7. 8911
  8. 10585
  9. 15841
  10. 29341
  11. 41041
  12. 46657
  13. 52633
  14. 62745
  15. 63973
  16. 75361

They are all odd! Indeed, korselt’s result implies that a Carmichael number $n$ can’t be a power of $2$ and therefore an even number must divide $n-1$, so $n$ is odd.

Now any time a new kind of number is defined, one simply must ask: are there infinitely many? Yes there are! In fact, William Alford, Andrew Granville, and Carl Pomerance showed that for sufficiently large $n$, there are at least $n^{2/7}$ Carmichael numbers. However, if $n=10^6$ then $n^{2/7}$ is about 51.795, though there are only 43 Carmichael numbers under $10^6$. Therefore, 10^6 isn’t sufficiently large.

Leave a Reply

Your email address will not be published. Required fields are marked *