Mersenne Prime
Definition
A Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form M_n = 2^n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied these numbers in the early 17th century.
History
The first four Mersenne primes (for n = 2, 3, 5, 7) were known in antiquity. The next three (for n = 13, 17, 19) were discovered in the early 17th century by Pietro Cataldi and Marin Mersenne, after whom the Mersenne primes are named. Mersenne primes were central to the development of number theory and the study of prime number distribution.
Properties
Mersenne primes have a number of interesting properties. For example, the exponent n must itself be a prime number. This is because if n = a·b, then 2^n − 1 = (2^a − 1)(2^(a(b−1)) + 2^(a(b−2)) + ... + 2^a + 1). This property makes Mersenne primes particularly interesting to number theorists.
Applications
Mersenne primes have many applications in the field of computer science. They are used in the generation of pseudorandom numbers, in the implementation of fast Fourier transforms, and in the design of some types of error-correcting codes. Mersenne primes are also used in the search for new prime numbers.
Search for Mersenne Primes
The search for new Mersenne primes has been a focus of computational number theory for many years. The largest known prime number is always a Mersenne prime. The search for these primes is facilitated by the Lucas–Lehmer primality test, an algorithm that is especially fast on binary computers.