If 2^n-1 is prime, n is prime [Proof]

If 2ⁿ-1 is a prime number, then n is also a prime number. Note that if 2ⁿ-1 is prime then it is called a Mersenne prime.

If 2ⁿ-1 is prime, then prove that n is prime

Question: Prove that if 2ⁿ-1 is prime, then n is prime.

Solution:

The given statement will be proved by the contrapositive method. So assume that n is not a prime number, that is, n is a composite number. So

n=pq

where p and q are integers greater than 1. Now,

2ⁿ-1 = 2^pq -1

= (2^p)^q -1

= (2^p-1) (2^p(q-1) + 2^p(q-2) + … +2^p+1).

As both 2^p-1 and 2^p(q-1) + 2^p(q-2) + … +2^p+1 are greater than 1, we conclude that 2ⁿ-1 is a composite number, not a prime number. This contradicts the given fact 2ⁿ-1 is prime. So our assumption is wrong. Hence we conclude:

If 2ⁿ-1 is a prime, then n is also a prime.

Read Also: Is 2 a Prime or a Composite Number?

Examples

We know that 31 is a prime number.

Note that 31=2⁵-1.

Here n=5 is a prime number. So 31=2⁵-1 is an example of a Mersenne prime number.

FAQs