3
$\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
  • 2
    $\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
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ According to prothsearch.com/fermat.html, it has been proven that all the fermat numbers from $F_5$ to $F_32$ are composite and it's not known whether there are any Fermat numbers other than the first 5 are prime. However, it it were like the old days with no technology, I wouldn't even know how to prove that $F_5$ wasn't the only Fermat composite. It's not that hard to prove that $F_5$ is composite or even find the factor of 641 in the first place because from my answer, it is obvious that all factors of it must be 1 more than a multiple of 128. $F_6$ would have been small enough $\endgroup$ – Timothy May 5 at 17:05
  • $\begingroup$ for me to have high hope of it being prime even. It would have been nice if it were like the old days and I didn't already know it was composite but now that they already proved them composite up to $F_32$, there's only about 1 chance in a billion of there being another Fermat prime. $\endgroup$ – Timothy May 5 at 17:08
  • $\begingroup$ I don't think this answer answers the question. I think it is obvious to the author that $2^m + 1$ can only be prime when $m$ is a power of 2. A number was actually only defined to be a Fermat number when it is of the form $2^{2^n} + 1$. Also, you gave no explanation at all for why the first 5 Fermat numbers are prime nor did you answer how you can't find one. It turns out that there is an explanation of them all being prime as described in my answer. $\endgroup$ – Timothy May 5 at 20:36
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Therefore, for example, to check if $F_4 = 65537$ is prime or not, just by trial division, all you need to check are primes of the form $64j+1$ that are below $\sqrt{F_4}$. There exists only one such prime, namely $193$. Since it does not work, $F_4$ is prime. As soon as you go to $F_5$, there are more potential divisors, and you quickly discover (as did Euler) that $5\cdot 128+1 = 641$ divides $F_5$. This comment is also contained in the much more recent answer by Timothy. $\endgroup$ – Jeppe Stig Nielsen Apr 26 at 16:36
  • $\begingroup$ @JeppeStigNielsen I thought it was worth explaining the reason why all factors of 65,537 are of the form 64k + 1. $\endgroup$ – Timothy May 5 at 20:11
  • $\begingroup$ @JeppeStigNielsen I thought of this question and already knew the answer to it so I Google searched it. I didn't stumble on it. That explains why I could think of such a good answer. $\endgroup$ – Timothy May 7 at 15:58

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.