Exercise 497Logic, sets and proofs › Proof techniquesL1Added 3 Nov 2026
Contrapositive with primes
#contrapositive#prime#divisibility
Statement
Prove: if is prime and , then is odd.
Hint
The contrapositive: if is even, then is not prime or .
Show solutionHide solution
Solution
Contrapositive. "If is prime and , then is odd" is equivalent to "if is even (and prime), then ".
Proof. If is even prime, for some . Since is prime and , either (so ) or is composite. Primality forces .
Conclusion. All primes are odd.