Question

Prove the following statements using either direct or contrapositive proof. Let \(n \in \mathbb{N}\). If \(2^{n}-1\) is prime, then \(n\) is prime.

Short answer

Through contrapositive proving, it has been shown that when a value for \(n\) is not prime, the value of \(2^n - 1\) will also not be prime. Thus, if \(2^n - 1\) is prime, then the value of \(n\) must be prime. This proves the given statement.

Step-by-step solution

Understanding contrapositive proof

The first step is to understand what a contrapositive proof entails. A statement and its contrapositive are logically equivalent, meaning that they are both true or both false. The contrapositive of a statement 'If P then Q' is 'If not Q then not P'. In this case, our statement P is 'If \(2^n-1\) is prime' and Q is '\(n\) is prime', thus the contrapositive is 'If \(n\) is not prime (i.e., \(n\) is composite), \(2^n-1\) is not prime'.

Proving contrapositive statement

The next step involves proving our contrapositive statement. Any composite number can be expressed as a product of two positive integers \(a\) and \(b\) with \(n=a*b\), and \(a, b > 1\). Then expand \(2^n\) using the properties of exponents to get \(2^{ab} = (2^{b})^a\). This expression can now be expressed as \((2^b-1+1)^a -1\). By using the binomial theorem, that states if \(n=m*l\), then \((x+y)^{m*l} = x^{m*l} + C(m*l,1)x^{m*l-1}*y+...\). Thus \((2^b-1+1)^a -1\) can be written as \( (2^b-1) * (2^{ab-b} + 2^{ab-2*b} + 2^{ab-3*b}+..+1)\) . From this it can be gathered that \(2^b-1\) is a factor of \(2^n - 1\), showing that \(2^n - 1\) is not prime.

Conclusion

Being able to show that the contrapositive statement 'If \(n\) is not prime, then \(2^n - 1\) is not prime' is true concludes our proof. If \(n\) is a composite number, then \(2^n - 1\) is not prime. Hence, the original statement 'If \(2^n - 1\) is prime, then \(n\) is prime' is also true, thereby proving the given problem statement.