I have been given the following problem:
Let n > 1 be a positive integer. Let P be the following statement:
If n is a prime number then $2^n – 1$ is a prime number
Write down the converse of the statement P. Is it always true? Justify your answer.
I have solved this part by using a proof by contradiction, in the same way that is shown in this question. However, this problem is followed up with the following:
Write down the contrapositive of the statement P.
Is it always true? Justify your answer.
From my understanding the contrapositive of P is:
If $2^n-1$ is not prime, then n is not prime
What I'm struggling with is how to go about proving this. Could I just use the same method as the previous part of the question (again, see here)? Or would I have to get the contrapositive of the contrapositive (resulting back in P) and prove that in some way?
Best Answer
I think you mean converse. We can use a proof by exhaustion to prove the converse and disprove the contrapositive. As @lulu pointed out in the comments, $2^{11}-1=2047$, which is composite, but $11$ is still prime, which means that $2^n-1$ does not need to be prime for $n$ to be prime. I found another example as well: $n=23$. I hope this answers your question. Don't hesitate to ask any questions in the comment section below.