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 the 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.