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?
Best Answer
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.