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 contrapositive statement of  x ∈ S ⇒ x ∈ P is x ∉ P ⇒

x ∉ S.

Now, we will prove the above contrapositive 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.