In the preface to his Cogitata Physica-Mathematica (1644), the French monk Marin Mersenne stated that the numbers 2n-1 were prime for
n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257
and were composite for all other positive integers n < 257. It was obvious to Mersenne's peers that he could not have tested all of these numbers (in fact he admitted as much), and they could not test them either. It took three centuries and several mathematical discoveries (such as the Lucas Lehmer test), before the exponents in Mersenne's conjecture had been completely checked. It was determined that he had made five errors (three primes omitted, two composites listed) and the correct list is:
n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127
Where did Mersenne get his list? Perhaps we find a hint in this quote from Dickson's history [Dickson19]:
In a letter to Tanner [L'intermediaire des math., 2, 1895, 317] Lucas stated that Mersenne (1644, 1647) implied that a necessary and sufficient condition that 2p-1 be a prime is that p be a prime of one of the forms 22 n+1, 22n+/-3, 22n+1-1. Tanner expressed his belief that the theorem was empirical and due to Frenicle, rather than to Fermat, and noted the sufficient condition would be false if 267-1 is composite [as is the case, Fauquembergue].
So whomever the source (Mersenne, Frenicle, or Fermat), there seems to be a belief that the exponents p of Mersenne's have a special form. (There is also a missing restriction on the size of the prime because they all knew 23-1 is prime, but 3 is not one of these forms.) If you check the numbers under 257, you will get Mersennes' list (sans 3) plus the prime 61.
Sadly, the conditions quoted above are neither necessary nor sufficient. The Mersenne numbers Mp are composite for the following primes p: 257=28+1, 1021=210-3, 67=26+3, and 8191=213-1 (so none of the "sufficient" conditions hold). Also, Mp is prime for p=89, but 89 can not be written in any of the listed forms.
Related pages (outside of this work)
- Mersenne primes (history, theorems, and lists)
- Dickson19 (Vol. 1, p28)
- L. E. Dickson, History of the theory of numbers, Carnegie Institute of Washington, 1919. Reprinted by Chelsea Publishing, New York, 1971.