Mersenne and Fermat Primes

The material we discussed in the previous entry actually prepares the reader very nicely for a discussion of Fermat and Mersenne primes.

Mersenne primes are primes of the form 2^n - 1.
Fermat primes are primes of the form 2^n + 1.

We can show very easily that if 2^n-1 is prime, n must also be prime. As otherwise, if n=ab, 2^a -1 divides 2^n - 1.

Similarly, if  2^n + 1 is a prime, n must be a power of 2, otherwise if n=(2^m)(2k+1), we have that (2^(2^m) + 1) divides  2^n + 1.

Mersenne primes are notable partially because they are easier to test for "prime-ness" than other numbers, the largest known prime is currently a Mersenne prime (The exponent is 57,885,161). , and they are also used in cryptography, in the "Mersenne Twister" pseudorandom number generator.  It is conjectured that there are infinitely Mersenne primes, but this has not yet been proven.

Fermat primes are somewhat more enigmatic, as Fermat conjectured that for n=2^k, for any k, one would get a prime number. However, this conjecture was believed to result from a computational error and was handily refuted by Euler, who showed that k=5 gives a composite number. We actually know no Fermat primes other than k=0,1,2,3,4.

There are plenty of very interesting open questions in mathematics regarding both Fermat and Mersenne primes.