Searching for Fermat primes

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₁ through F₄ are prime and that F₅ through F₁₄ 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₁₄ has 4,933 digits, for example.

The Fermat numbers for n = 5 to 32 are known to be composite. Nobody knows whether F₃₃ 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.