How to check the primality of $2^n + 1$?

Question

With Mersenne Numbers, if $M = 2^n - 1$ is prime, $n$ is prime.

Is there a trick (may be similar to that of Mersenne) to check the primality of $2^n + 1$?

Answer 1

As far as I know (which, granted, doesn't necessarily mean much), the best test is

If $n=1,2,4,8$ or $16$, then $2^n+1$ is prime. Otherwise, probably not.

It is known (and not difficult to show) that $n$ must be a power of $2$, but apart from the five powers of $2$ mentioned above, no such primes are known.

Numbers of the form $2^{2^k}+1$ are known as Fermat numbers, and the Fermat numbers that are also primes are known as Fermat primes.

That being said, it wouldn't surprise me if number theorists have come up with efficient ways of checking the primality of Fermat numbers, like the Lucas–Lehmer test for Mersenne primes. It's just that they have yet to yield anything.

Answer 2

Worth remarking: If a prime $p$ divides $2^{2^n}+1$ then $2$ has order $2^{n+1}\pmod p$. This implies that $2^{n+1}\,|\,p-1$, which cuts down the search considerably.

As an example, consider $n=5$. To try to find a prime dividing $2^{32}+1$ we look for primes $p\equiv 1 \pmod {64}$. You can disregard the Fermat primes in that list, as the Fermat numbers are relatively prime. This leads you to try $641$ fairly quickly, and that factor works.

Answer 3

A deterministic test for Fermat numbers is Pépin's test:

Let $F_n=2^{2^n}+1$ with $n > 0$, then $F_n$ is prime if and only if $3^{(F_n-1)/2}\equiv-1\pmod{F_n}.$

Pépin's test is a special case of the Solovay–Strassen primality test base 3. In the general case for testing arbitrary odd numbers and arbitrary bases that test is probalistic.