Skip to main content

Subsection 8.4.6 Mersenne Numbers

Here’s the Mersenne numbers table again, this time with all the prime numbers shown in red:

Table 8.4.3.
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2n-1 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383

Consider two statements:

  1. If n is prime, then 2n-1 is prime.

  2. If 2n-1 is prime, then n is prime. (Alternatively, if n is not prime, then 2n-1 is not prime.)

Think about them. Do they appear to be true?

Exercises Exercises

Exercise Group.

Here’s the Mersenne numbers table again, this time with all the prime numbers shown in red:

Table 8.4.4.
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2n-1 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383

Just on the basis of the examples shown in the table above, what can you say about these two statements:

Part 1.

Statement 1 (If n is prime, then 2n-1 is prime.):

  1. Could be true or it could be false. Either case would be consistent with the examples in the table.

  2. Must be true (i.e,. the examples in the table prove that it must be true.)

  3. Is not true. The table contains a counterexample to the universal claim.

Answer.

Correct answer is C

Solution.
Explanation: Statement 1 is not true. 11 is prime, but 211-1 = 2047 isn’t prime.
Part 2.

Statement 2 (If 2n-1 is prime, then n is prime.):

  1. Could be true or it could be false. Either case would be consistent with the examples in the table.

  2. Must be true (i.e,. the examples in the table prove that it must be true.)

  3. Is not true. The table contains a counterexample to the universal claim.

Answer.
Correct answer is A
Solution.
Explanation: Statement 2 could turn out to be either true or false. In the table, every column that has 2n-1 prime also has n is prime. So the claim might be true. Of course, we can’t prove a universal claim with a list of examples. It turns out, though, that it is possible to prove this claim.