Exercise 4

Formulate a proof by contradiction that shows that for all integers x > 2 the proposition (P (x) ∧ ¬Q(x)) is false. Hence show the following: Let > 2 be an integer. Then x can not be a prime and gcd(x, 2) != 1.

Proof: Assume for the sake of contradiction that there exists an integer x > 2 such that P(x) ∧ ¬Q(x) is true. By definition of P(x) and ¬Q(x), this means that x is a prime and gcd(x, 2) != 1.

However, this contradicts the fact that all primes greater than 2 are odd. This is because the only way for gcd(x, 2) to not equal 1 is for x to be even. But if x is even, it cannot be prime. Therefore, the assumption that P(x) ∧ ¬Q(x) is true leads to a contradiction and must be false.

Hence, we can conclude that for all integers x > 2, x cannot be a prime and gcd(x, 2) != 1.