Why are the first 5 Fermat numbers prime?

Question

The $n$th Fermat number $F_n$ is defined as $F_n = 2^{2^n}+1$. The first five Fermat numbers, $F_0,F_1,F_2,F_3,F_4$, are all prime. Why is this?

It seems like a fairly surprising coincidence that all five of these are prime. The prime number theorem predicts that the density of prime numbers near $m$ is about $1/\log m$. Therefore, as a crude heuristic, we expect that $F_n$ has about a $1/\log F_n$ "probability" of being prime (if it behaved like a random number of that size). Now

$${1 \over \log F_1} \times {1 \over \log F_2} \times {1 \over \log F_3} \times {1 \over \log F_4} \approx {1 \over 281}.$$

So, it seems like a rather unexpected coincidence that all of these should be prime. I know there are some weaknesses in this argument, but even after them, it still feels suggestive that perhaps there is something deeper going on.

Is there an explanation why this fact (that the first five Fermat numbers are prime) is not as surprising as it might first seem? For instance, are there some additional properties of Fermat numbers that make them "more likely" to be prime than a random number of that size? (Perhaps the set of possible divisors is restricted to a much smaller set than for a general number, and this affects the density?)

---

I see a comment arguing that the heuristic is inaccurate for small numbers. But that's not what I find when I try some examples. For instance, let's compute $f(m)$, the fraction of numbers in the range $[m/\sqrt{2},\sqrt{2}m)$ that are prime. We find $f(5) = 0.5$ and $f(17)=0.33$ and $f(257)=0.16$, whereas the heuristic gives $1/\log 5 = 0.62$ and $1/\log 17 = 0.35$ and $1/\log 257 = 0.18$. Pretty close. (The interval $[m/\sqrt{2},\sqrt{2}m)$ is arbitrarily chosen to be approximately centered around $m$ and to have the upper value be about twice the lower value; but it can be replaced with any other reasonable choice without appreciably changing the result.) So this "crude heuristic" is actually quite accurate even for small numbers, and can't be the explanation for the situation.

Or, let me put it another way. Suppose I replace the crude heuristic above with a more accurate estimate, where I use $f(m)$ as the density of prime numbers near $m$. Here $f(m)$ is calculated empirically as shown above, not by any asymptotic estimate relying upon the prime number theorem. Now through calculation I find

$$f(5) \times f(17) \times f(257) \times f(65537) \approx 0.5 \times 0.33 \times 0.16 \times 0.09 \approx {1 \over 405}.$$

So the explanation is not failure of the prime number theorem to apply to small numbers. Indeed, if we use exact estimates rather than asymptotic estimates, it still appears to be a somewhat surprising coincidence that all of $F_0,\dots,F_4$ are prime, if we assume that the Fermat numbers behave like random numbers of a similar size.

Of course, the most obvious explanation is that Fermat numbers probably don't behave like random numbers of a similar size, when it comes to the "probability" of being prime -- perhaps they are "more likely" to be prime than a random number of a similar size. But my question is: Is this so, and if so, why? Is there some deeper phenomenom that explains why Fermat numbers are "more likely" to be prime than a random number of a similar size, and if so, what is that?

Answer 1

Actually, the density of prime numbers varies as the reciprocal of the log.

It is a well known theorem that the multiplication modulo group of any prime number is cyclic. For any positive integer $n$, the only possible prime factors of $2^{2^n} + 1$ must be 1 more than a multiple of $2^{n + 1}$. For any prime number of the form $k \times 2^{n + 1} + 1$, $k \times 2^{n + 1} + 1$ is a factor of $2^{2^n} + 1$ if and only if $2^{2^n}$ is congruent to $-1$ modulo $k \times 2^{n + 1} + 1$. The probability of $2^{2^n}$ being congruent to $-1$ modulo $k \times 2^{n + 1} + 1$ is $\frac{1}{2k}$. That seems way higher than you would normally expect the probability of $k \times 2^{n + 1} + 1$ being a factor of $2^{2^n} + 1$ to be, which explains why it is suspected that there are only finitely many Fermat primes.

It turns out that there is also a theorem that for any odd prime $p$, 2 is a square modulo $p$ if and only if $p$ is congruent to 1 or 7 modulo 8. This skews the probabilities so that the probability of $k \times 2^{n + 1} + 1$ being a factor of $2^{2^n} + 1$ is $\frac{1}{k}$ when $k$ is even and 0 when $k$ is odd. 3 and 5 are not congruent to 1 or 7 modulo 8 so 2 is not a square modulo them. All factors of 17 must be of the form $16k + 1$ but the first nontrivial number of that form is 17 itself. All factors of 257 must be of the form $32k + 1$ but 33 is already more than the square root of 257. Finally, all factors of 65,537 must be of the form $64k + 1$. The only prime number of that form to test that's less than its square root is 193. By convention, we say that 64 is congruent to $-\frac{1}{3}$ modulo 193 because it's the multiplicative inverse of -3 in $Z_{193}$. We see that 256 is congruent to $-\frac{4}{3}$ modulo 193 and so 65,536 is congruent to $\frac{16}{9}$ modulo 193 which is not -1 modulo 193.

Answer 2

First off the prime density heuristic is for uniformly random numbers in a given interval. Fermat numbers as special for the following reason. You can show that for a of the form $M=2^m+1$: if $M$ is prime, then $m=2^k$ for some $k$. You can find a proof of this fact in the first section here. Thus at the very least demanding $m=2^k$ might raise your chances for finding a prime. After all, you are excluding all numbers of the form $2^m+1$ where $m\neq 2^k$. There's not that many of these numbers in a given interval but it's a start.

The next reason is somewhat tautological: Fermat and Euler got interested in these numbers precisely for the reason you mentioned: the first 5 are prime. Euler in a tour-de-force showed that $2^{2^5}+1$ is not prime, thereby refuting Fermat's conjecture that all these numbers are prime. You can imagine that interest in these numbers grew from the fact that it was quite non-trivial to figure out if $2^{2^5}+1$ is prime or not as these numbers grow very fast.

Anyways, you can find plenty of examples that generate prime numbers like prime polynomials and Mill's constant, which will similarly defy your intuition about prime density.

Answer 3

I know this is pretty late, but I wanted to add onto Alex's answer:

One of the results here says that the prime factors of $2^{2^n}+1$ must be equivalent to $1 \bmod 2^{n+2}$. For example, $2^{16}+1$ can only have factors that are $1 \bmod 64$, lowering the proportion of prospective factors significantly.

Answer 4

Note that prime powers in general tend to be good anchor points for finding primes, for the reasons already excellently explained. I just wanted to point out that this type of observation is not specific to $2$ as a base.

E.g. consider $3^{2^n}+2$ (since with $+1$ it would always be even), which is prime for its first four $n$ values, giving $\{5,11,83,6563\}$.

Substantially more revealing is perhaps $$\frac{1}{2}\left(3^{2^n}+1\right).$$

Like the last example, it has the advantage of being necessarily coprime to both $2$ and $3$ immediately, but of course it also grows much faster than $2^{2^n}$. Six of its first seven values are prime:

$$ \begin{array}{|l|l|} \hline n & f(n)\text{, factored} \\ \hline 0 & 2 \\ \hline 1 & 5 \\ \hline 2 & 41 \\ \hline 3 & \color{red}{17\times193} \\ \hline 4 & 21523361 \\ \hline 5 & 926510094425921 \\ \hline 6 & 1716841910146256242328924544641 \\ \hline \end{array} $$

AFAIK, not including the Mersennes, many prime record-holders are also variations on forms like $k \cdot p^q+c$ with certain advantageous values plugged in.