1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Your probability heuristic is valid for really large numbers $m$. The first four fermat numbers are all relatively small. $\endgroup$ – Umberto P. Jun 6 '16 at 23:55
  • $\begingroup$ @UmbertoP., actually, it's reasonably accurate for numbers of this size, too. Just try it! $\endgroup$ – D.W. Jun 6 '16 at 23:58
  • $\begingroup$ It's not "fair" to take a number with a high probability of being prime to begin with (for example, $2^p-1$ for some prime number $p$), and expect the same probability predicted by the prime number theorem for any random number. If you know nothing about that number, then fine - use the PNT to predict its likelihood of being prime. But if you already have some pre-knowledge about it... well, that changes the prediction, now doesn't it? $\endgroup$ – barak manos Jun 7 '16 at 0:04
  • 1
    $\begingroup$ For $n \geqslant 2$, if $p$ is a prime dividing $F_n$, then $p \equiv 1 \pmod{2^{n+2}}$. (The order of $2$ modulo $p$ is $2^{n+1}$, and $2$ is a quadratic residue, so there is an element of order $2^{n+2}$ modulo $p$.) If $F_n$ is composite, its smallest prime divisor is $< 2^{2^{n-1}}$. Thus $F_4$ is the first Fermat number that has a fighting chance of being composite, with the only candidate $p = 193$ to check. It's maybe more surprising that none of the next Fermat numbers is prime. $\endgroup$ – Daniel Fischer Jun 7 '16 at 2:00
  • 1
    $\begingroup$ Seconding Daniel's comment. See here for a more general result. $\endgroup$ – Jyrki Lahtonen Jun 9 '16 at 17:37
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.