Is there a special name for primes $p = 2^n+1$ and what is the largest known to date?

Question

I'm reading a paper by Pohlig and Hellman on computing discrete logarithms, they use primes $p = 2^n+1$ as a simple special case to explain their algorithm. I'm curious, is there a special name for these primes and what's the largest known prime with this structure? In the paper they mentioned that $2^{16}+1$ is the largest known, but the paper is from 1978.

Answer 1

Yes, these primes are Fermat primes. The Wikipedia page states that

If $2^k+1$ is prime and $k>0$ it can be shown that $k$ is a power of $2$

And also

As of 2016, the only known Fermat primes are $F_0, F_1, F_2, F_3$ and $F_4$.

So the largest known is $2^{2^4}+1 = 65537$.

This article [Tsang, 2010] might be interesting reading for you!

Answer 2

Let $n$ be a positive integer, $n=ab$ say, with $1 \leqslant a < n$, $1 < b \leqslant n$, and $b$ odd, where apart from the trivial case $a=1$, we require $a$ to be even. We have that

$$u^{ab}+v^{ab}=(u^a+v^a)\sum_{k=1}^{b}(-1)^{k+1}u^{a(b-k)}v^{a(k-1)}$$ Let $u=2$, $v=1$, then divide to get $$\frac{2^{ab}+1}{2^a+1}=\sum_{k=1}^{b} (-1)^{k+1}2^{a(b-k)}$$ Then since $(2^a+1)\mid(2^{ab}+1)$, where $(2^a+1)>1$, we must have $2^n+1$ composite. Hence if $2^n+1$ is prime, then $n$ must be a power of $2$. These are the Fermat primes of the form $F_n=2^{2^n}+1$ and of which $2^{2^4}+1 = 65537$ is the largest known. Here are the first six Fermat numbers, where at $F_5$ (factored by Euler in 1732) they turn composite (maybe with no primes after $F_4$ in the sequence!): \begin{align*} F_0&=2^{2^0}+1=3=p_{2}\\ F_1&=2^{2^1}+1=5=p_{3}\\ F_2&=2^{2^2}+1=17=p_{7}\\ F_3&=2^{2^3}+1=257=p_{55}\\ F_4&=2^{2^4}+1=65537=p_{6543}\\ F_5&=2^{2^5}+1=4294967297=641\cdot6700417=p_{116}\cdot p_{457523}\\ \end{align*}