Intuitively, what separates Mersenne primes from Fermat primes?

Question

A Mersenne prime is a prime of the form $2^n-1$.

A Fermat prime is a prime of the form $2^n+1$.

Despite the two being superficially very similar, it is conjectured that there are infinitely many Mersenne primes but only finitely many Fermat primes.

Is there an intuition that can help me appreciate the nature of that seemingly paradoxical difference?

Answer 1

It's easy to get that for Mersenne primes $n$ must be prime, and for Fermat primes $n$ must be a power of 2. Let's go to the hueristics.

Being prime is of course not random, but it is often useful to think of it as a random property of numbers. The prime number theorem tells us that a large number $n$ is prime with probability approximately $\frac{1}{ln(n)}$, using this lets compute the expected number of Mersenne primes throwing out the ones we know can't be prime.

$$\sum_{p \text{ prime}} \frac{1}{ln(2^p-1)} \sim c\sum_{p \text{ prime}}\frac{1}{p}$$

Which we know diverges, hence we expect infinitely many Mersenne primes. Moreover the rate of divergence tells us about how many Mersenne primes to expect up to a certain size. On the other hand, if we do the same analysis for Fermat primes:

$$\sum_{n} \frac{1}{ln(2^{2^n}+1)} \sim c\sum_{n}\frac{1}{2^n}$$

We get a convergent geometric series, hence we only expect finitely many such primes.

Answer 2

There is this observation:

$2^n-1$ is a candidate prime (no obvious factors) whenever $n$ is prime.

$2^n+1$ is a candidate prime only when $n=2^r$ (if $n$ is divisible by an odd prime $p$, so $n=pq$ one can extract a factor $2^q+1$, because $x^p+1$ has a factor $x+1$ - use $x=2^q$)

The candidates for Mersenne Primes occur considerably more frequently than the candidates for Fermat Primes.

Answer 3

Nearly everything:

Exponent required

Mersenne prime exponents only, and not on first kind cunningham chains except two places.

Fermat power of two exponent

Factor type

Mersenne $q=2kp+1$ for prime exponent $p$, $q\equiv \pm 1 \pmod 8$ restricting $k$ ( modified P-1 used as well as TF)

Fermat $j\cdot 2^{n+2} +1$ with restrictions on $j$ fully dependent on $n$

Primality test

Mersenne iterating $x^2-2$ from a starting value of 4, $p-2$ times, attempting to show $s_{p-2}\equiv 0\pmod {2^p-1}$ ( traditionally, now pretested via a PRP and checked with error checking)

Fermat repeated squaring to show $3^{{F_n-1 \over 2}}\equiv -1\pmod {F_n}$

Growth

Mersenne numbers( non prime exponent definition) double and add 1.

Fermat numbers $F_n=(F_{n-1}-1)^2+1$ or in comparison to a Double Mersenne ( a Mersenne number with Mersenne exponent) $F_n=2\cdot M_{M_n}+3$

Double Mersenne facts : $M_{M_n}=2M_{M_{n-1}}^2+4\cdot M_{M_{n-1}}+1$ prime final exponents $p$ have factors that are of form $2j(2kp+1)+1= 4kjp+(2j+1)$

There are heuristics you can throw around, but in the end heuristic arguments are hard to test for Fermat numbers due to size ( We'll probably factor $M_{M_{127}}$ before $F_{127}$)

Answer 4

I think Nate's answer is missing something vital. Actually, a Fermat number is a number of the form $2^{2^n} + 1$ whereas a Mersenne number is any number of the form $2^n - 1$. It can easily be shown that $2^n + 1$ can only be prime when $n$ is a power of 2 and $2^n - 1$ can only be prime when $n$ is a prime number. Despite this, n still doesn't have to be prime in order for $2^n - 1$ to be called a Mersenne number. There is something extra special about Fermat numbers and Mersenne numbers with prime exponent that may make you question its probability of being prime as I will describe later. It is a well known theorem that the multiplication modulo group of any prime number is a cyclic group of order one less than that prime number.

The only possible factors of $2^{2^n} + 1$ are 1 more than a multiple of $2^{n + 1}$. I believe I once read on the internet that Fermat conjectured that all Fermat are prime because of the extreme restrictions on what their prime factors can be. It turns out that the argument is flawed. I believe the proportion of prime numbers that are 1 more than a multiple of $2^{n + 1}$ is $2^{-n}$. When $(k \times 2^{n + 1}) + 1$ is prime, the only way for it to be a factor of $2^{2^n} + 1$ is when $2^n$ is congruent to -1 modulo $(k \times 2^{n + 1}) + 1$ and the probability of that is $\frac{1}{2k}$.

There is actually a theorem that for any odd prime number p, 2 is a square modulo p when and only when p is congruent to 1 or 7 modulo 8. This skews the probabilities so that when k is odd, the probability of $2^n$ being congruent to -1 modulo $(k \times 2^{n + 1}) + 1$ is zero and when k is even, the probability of $2^n$ being congruent to -1 modulo $(k \times 2^{n + 1}) + 1$ is $\frac{1}{k}$.

Similarly, for any odd prime number $p$, all prime factors of $2^p - 1$ must be 1 more than a multiple of 2p. When $2pk + 1$ is congruent to 3 or 5 modulo 8, the probability of $2pk + 1$ being a factor of $2^p - 1$ is zero. When $2pk + 1$ is congruent to 1 or 7 modulo 8, the probability of $2^p$ being congruent to 1 modulo $2pk + 1$ is $\frac{1}{k}$.