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

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

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

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

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,

2n-1 = 2pq -1

= (2p)q -1

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

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

If 2n-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=25-1.

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

FAQs

Q1: If 2n-1 is a prime, then is n prime or composite?

Answer: If 2n-1 is a prime, then n is always a prime number.

Share via:
WhatsApp Group Join Now
Telegram Group Join Now