Skip to main content

Subsection 8.4.7 Mersenne Primes

Hundreds of years ago, some mathematicians believed that statement 1 above (i, e., if n is prime, then 2n-1 is prime) was true. Then, in 1536, Hudalricus Regius refuted the claim by showing (as we just did) a single counterexample: 211-1 = 2047 is not prime.

But that was not the end of false conjectures about these numbers. The eponymous monk, Marin Mersenne, in 1644, made the claim that Mersenne numbers are prime if n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, but are composite for all other positive integers n ≤ 257. Mersenne’s claim was shown to be false by counterexample, over two hundred years later, when it was discovered that 261-1 is also prime. Later discoveries showed other ways in which Mersenne was wrong. The correct list of values of n ≤ 257 such that 2n-1 is prime is 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127.

48 Mersenne primes are now known. It’s conjectured that there are infinitely many of them. Proving this will require more than just a longer list of them, however.

The story of these numbers is an excellent example of what proof by example/counterexample can do and what it cannot do:

  • A universal claim can be refuted by a single counterexample.

  • A universal claim cannot be proved even by a long list of examples.

Nifty Aside

To find out more about Mersenne numbers, visit http://primes.utm.edu/mersenne/.

Exercises Exercises

1.

1. Consider the claim:

[1] ∀x (Prime(x) → ¬Prime(x + 1))

Which of the following statements is true:

  1. [1] can be proved with a single example.

  2. [1] is true but cannot be proved with a single example.

  3. [1] can be proven to be false with a single counterexample.

  4. [1] is false but cannot be proven so with a single counterexample.

Answer.
Correct answer is C
Solution.
Explanation: Here’s one counterexample: 2 is prime but so is 3. Now think about this question: Are there any other counterexamples to this claim? Click here to see the answer to that question. The 2, 3 case is the only counterexample. All primes except 2 are odd. That means that their successors are even and thus not prime.

2.

Consider the claim:

[1] Every sequence of 10 consecutive integers contains at least one prime number.

For example, the sequence 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 actually contains 4 primes (11, 13, 17, 19)

Which of the following statements is true:

  1. [1] can be proved with a single example.

  2. [1] is true but cannot be proved with a single example.

  3. [1] can be proven to be false with a single counterexample.

  4. [1] is false but cannot be proven so with a single counterexample.

Answer.
Correct answer is C
Solution.

Explanation: [1] is false and a single counterexample suffices to show that. The problem is that it’s necessary to look at some reasonably large numbers to find such an example. The smallest example is the sequence 114, 115, 116, 117, 118, 119, 120, 121, 122, 123. You probably wouldn’t want to do this by hand, but it’s straightforward to write a program to do it. If you want to try your hand, write a program to find the next sequence that contains none of the numbers in this one.

By the way, we’ll soon (in the section on Proof by Construction) prove a more general statement that is suggested by the fact that we could find a sequence of 10 composite numbers. We’ll prove that, for any value n, there exists a sequence of n consecutive composite numbers.