Question

Let P be the set of prime numbers and let S = {t | 2^t – 1 is a prime}. Prove that S ⊂ P.

Answer 1

Now the equivalent contra positive statement of x ∈ S ⇒ x ∈ P is x ∉ P ⇒ x ∉ S.

Now, we will prove the above contra positive statement by contradiction method 

Let x ∉ P 

⇒ x is a composite number 

Let us now assume that x ∈ S 

⇒ 2^x – 1 = m (where m is a prime number) 

⇒ 2^x = m + 1 

Which is not true for all composite number, say for x = 4 because 

2⁴ = 16 which can not be equal to the sum of any prime number m and 1. 

Thus, we arrive at a contradiction 

⇒ x ∉ S. 

Thus, when x ∉ P, we arrive at x ∉ S 

So S ⊂ P