What makes the Mersenne primes formula more special than any of these formulas?

Question

Mersenne Primes Formula $2^n-1$ gives false results just like any of those ones:

$3^n-2, 4^n-3, P_1\cdot P_2+P_1+P_2$, or $5^n-4$ and so on..

I think that each of those formulas(including Mersenne's) is just giving random odd numbers -that may or may not be primes- and doesn't have anything special.. So the question is "What's the special -functional- thing about that Mersenne Primes formula?"

Answer 1

One special thing about Mersenne primes is that each one leads to a perfect number if you multiply it by $2^{n-1}$.

Answer 2

There are techniques for testing Mersenne numbers for primality, techniques that work only for Mersenne numbers and not for any of the other numbers you mention. This results in the largest known primes being Mersenne primes.

Answer 3

First of all, a necessary condition that $2^n-1$ be prime is that $n$ itself is prime.

Second, as stated in good old Wikipedia, "The best method presently known for testing the primality of Mersenne numbers is the Lucas–Lehmer primality test. Specifically, it can be shown that for prime $p > 2$, $M_p = 2^p − 1$ is prime if and only if $M_p$ divides $S_{p−2}$, where $S_0 = 4$ and, for $k > 0$, $S_k = S_{k-1}^2-2$." This test can be done very efficiently, so the primality of $M_p$ can be checked much more quickly that other numbers of the same size.

Answer 4

Not only Mersenne numbers formula is special. The Fermat numbers $2^{2^n}+1$ also can be proven prime thanks to the LLT method (LLT = Lucas-Lehmer Test) using seed $5$ which is equivalent to the Pépin's test. It takes nearly exactly the same time to prove that a Mersenne number and a Fermat number are primes if they have nearly the same size. However, Fermat numbers are very rare since they grow very very fast.

See: http://arxiv.org/PS_cache/arxiv/pdf/0705/0705.3664v1.pdf for a proof of the LLT for Fermat numbers, and see: http://www.ejpam.com/index.php/ejpam/article/viewArticle/245 for a proof of the equivalence between Pépin's test and LLT for Mersenne numbers. For a proof of equivalence of Pépin's test and LLT for Fermat numbers, see bottom of page 4 of: http://tony.reix.free.fr/Mersenne/PrimalityTest1FermatNumbers.pdf .