Mersenne prime

A Mersenne number is a number of the form. In particular, we denote by the -th Mersenne number. The first eight Mersenne numbers are

The prime numbers among the Mersenne numbers are called Mersenne primes. The first eight Mersenne primes are

The Mersenne defined in base 2 show up in the binary system as ones columns, ie Are charged, consisting exclusively of ones. The n-th Mersenne number is a number in the binary system with n ones ( example: M3 = 7 = 1112). Mersenne numbers are in binary to the Zahlenpalindromen, Mersenne primes accordingly to the Primzahlpalindromen.

Your name, these primes by the French monk Marin Mersenne and priest (1588 - 1648), who claimed in the preface of his Cogitata Physico - Mathematica that for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257 is a prime number.

However, he was wrong in the numbers and and overlooked the Mersenne primes, and. That is not a prime, Édouard Lucas has shown in 1876, but only in 1903 the mathematician Frank Nelson Cole could name the prime factors of this number. In order to prove that is not a prime, in 1932 an early calculating machine was used. When the number is possibly due to a read error on the part of Mersenne from his correspondence with Bernard Frénicle de Bessy and Pierre de Fermat, which he mistook for.

Mersenne numbers are also found in the Mersenne Twister, a pseudo-random number generator.

History

Mersenne numbers were first studied in the ancient world in the context of perfect numbers. A natural number is called perfect if the sum of its proper divisors is equal to (example: 6 = 1 2 3). Euclid already showed that, when 2n - 1 is a prime number, the number 2 n - 1 × (2n - 1 ) is completely (n = 2 gives the number 6). 2000 years later, the Euler inversion for even perfect numbers shown: every even perfect number is of the form 2n -1 · (2n - 1), 2n - 1 is a prime.

The first four perfect numbers 6, 28, 496 and 8128 were already known in antiquity. The search for other perfect numbers motivated the search for other Mersenne primes. The most important thing to be observed property is as follows:

It follows immediately that the exponent p a Mersenne prime is a prime number itself. Due to this property, the search for Mersenne primes is facilitated because only Mersenne numbers must be viewed with prime exponent.

However, the reverse is false, since, for example, M11 = 2047 = 23 · 89 is not prime.

Mersenne primes are rare: to date (2013 ) have been found only 48 of them. There is a particularly simple primality test for them, the largest known primes are Mersenne primes.

Also by the GIMPS project the 43rd Mersenne prime is discovered in December: M ( 30,402,457 ) has 9,152,052 points.

Divisibility properties of Mersenne numbers

Over its long history, many results have been found over Mersenne numbers. Besides the already mentioned basic Teilbarkeitseigenschaft ( r divides the number n, so Mr is a divisor of Mn), there are, for example, the following results:

• N is an even number, and n 1 prime, n is a divisor of M n 1, for example, M10 = 1023 = 11/03/31, M12 = 4095 = 3 ² · 5.7.13.

• N is an odd prime number and q is a prime factor of Mn, it shall q ≡ 1 (mod 2n ) and q ≡ ± 1 (mod 8). Example: M11 = 2047 = 23.89 and 23 = 2:11 1; 89 = 4.2.11 1.

• If p is a prime number with p ≡ 3 ( mod 4 ), then the following equivalence holds: 2p 1 divides the Mersenne number Mp if and only if 2p 1 is prime. Example: 11 is prime and leaves a remainder of 3 when divided by 4, since 23 (as a result of 2.11 1) is prime, it follows that. 23 divides the Mersenne number M11 = 2047 This statement was formulated by Leonhard Euler, later proved by Joseph -Louis Lagrange, however (see also Sophie Germain prime ).

• If Mp is a prime number > 3, then Mp 2 is not a prime ( ie divisible by 3 ). Mersenne primes are therefore not suitable as the smaller prime a prime twin.

• N = 2m ( m> 0), is the product of the Mn Fermat numbers F0 to Fm -1. Example: M16 = F0 · F1 · F2 · F3 = 3.5.17.257.

The search for Mersenne primes

For the generation of prime number records to Mersenne primes are in many respects especially good because ( a) composite exponent can be ignored because they do not generate prime numbers, and therefore the list of candidates for the exponent p can be created with prime generators easily, (b) can be separated from that list as described above, the Sophie Germain primes with p ≡ 3 ( mod 4 ) ( such as p = 11 → divider 23), ( c) by the functional relationship of the order the prime exponentially - namely to the base two - with the argument p increases, so you get fast very large numbers, ( d) is a simple and effective primality test available with the Lucas -Lehmer test described below.

The Lucas- Lehmer test

→ Main article: Lucas- Lehmer test

This test is a specially tailored to Mersenne prime numbers test on the work of Édouard Lucas from the period 1870 - 1876 is based and was supplemented in 1930 by Derrick Lehmer.

It works as follows:

GIMPS: The Great Internet Mersenne Prime Search

Until now (2013 ) one knows 48 Mersenne primes. With the help of computers trying to find more Mersenne primes. Since it is very large numbers - the 48th Mersenne prime has more than 17 million digits in the decimal system - are the calculations (time and organizational ) consuming. Arithmetic operations with such large numbers of computers are not supported by default. You have to save the numbers in large fields and thus program the necessary basic arithmetic. This results in long program run times.

GIMPS (English: Great Internet Mersenne Prime Search ) therefore seeks to involve as many computers in the calculations around the world. The necessary software (Prime95 ) was created by George Woltman and Scott Kurowski and it is available for a variety of computer platforms (Windows, Unix, Linux ... ).

Anyone can join, provided they hold a computer with (temporarily) free CPU capacity. Therefore one must be downloaded from the website and then install the software. After you enroll in gimps and can give a number that you should investigate. When the calculations are completed ( usually after several months ) to inform about the result back in gimps. You get it over the computer analysis also indicated probabilities: the probability of finding a prime number ( very small, less than 1% ); the probability of finding a factor (greater than). This probability will make the prospects for finding a prime number significantly.

List of all known Mersenne primes

So far (as of February 23, 2014 ) is not excluded that it = 57,885,161 in addition to the four known Mersenne primes are still more between n = 30,402,457 and n; therefore, the numbering from No. 44 still uncertain ( and '?' provided with a ).

Open Questions

As so often in number theory there are also Mersenne numbers unsolved problems that are very easy to formulate:

• Are there infinitely many Mersenne primes? Man suspected because of plausible heuristics that there are about c · ln ( x) many Mersenne primes Mp are with p

• More specifically, the assumption that the HW Lenstra and C. Pomerance lined up independently, correctly, that it asymptotically are many Mersenne primes that are less than or equal to x?

• Conversely, there are infinitely many Mersenne numbers Mp with p prime, are not prime? Again, it is assumed as an answer, yes. This would, for example follow from the assumption that there are infinitely many Sophie Germain primes that are congruent to 3 modulo 4.

• Are all Mersenne numbers Mp with p prime square-free, ie, occurs in the prime factorization of the number of each prime factor only once before? You could not even prove so far that this is true for infinitely many Mersenne numbers.

• Does the " new Mersenne conjecture "? The sequence of Mersenne primes Mersenne stated, suggests that he meant that a Mersenne number Mp with p prime if and only prime if p = 2k ± 1 or p = 4k ± 3 Since this statement does not apply, put P. Bateman, J. Selfridge and S. Wagstaff on the new Mersenne conjecture.

• Are all elements of the sequence C (0) = 2 C (k 1) = 2C (k) - 1 primes? The stronger assumption that all numbers MMp primes for which Mp is prime, could be disproved in 1957 by Raphael Robinson. These latter figures are called double Mersenne numbers ( OEIS, A077585 ). So far, double Mersenne primes only for p = 2, 3, 5, 7 known ( OEIS, A077586 ); p = 13, 17, 19 and 31, small factors have been found. Whether there are more or even infinitely many double Mersenne primes, remains unknown.