Fermat numbers have the form

Fermat numbers are prime if *n* = 0, 1, 2, 3, or 4. Nobody has confirmed that any other Fermat numbers are prime. Maybe there are only five Fermat primes and we’ve found all of them. But there might be infinitely many Fermat primes. Nobody knows.

There’s a specialized test for checking whether a Fermat number is prime, Pépin’s test. It says that for *n* ≥ 1, the Fermat number *F*_{n} is prime if and only if

We can verify fairly quickly that *F*_{1} through *F*_{4} are prime and that *F*_{5} through *F*_{14} are not with the following Python code.

def pepin(n): x = 2**(2**n - 1) y = 2*x return y == pow(3, x, y+1) for i in range(1, 15): print(pepin(i))

After that the algorithm gets noticeably slower.

We have an efficient algorithm for testing whether Fermat numbers are prime, efficient relative to the size of numbers involved. But the size of the Fermat numbers is growing exponentially. The number of digits in *F*_{n} is

So *F*_{14} has 4,933 digits, for example.

The Fermat numbers for *n* = 5 to 32 are known to be composite. Nobody knows whether *F*_{33} is prime. In principle you could find out by using Pépin’s test, but the number you’d need to test has 2,585,827,973 digits, and that will take a while. The problem is not so much that the exponent is so big but that the modulus is also very big.

The next post presents an analogous test for whether a Mersenne number is prime.

The way in which Gauss discovered that F5 is composite is wonderful- and a great lesson on how human calculators are not necessarily obsolete in the electronic age, and perhaps can be good for some significant “insight”. If no one can find it, I’ll copy the passage from Hardy and Wright.