Let x and y be integers. Prove that if $7 \nmid$ xy, then 7 $\nmid$ and $7 \nmid$ y.

I want to prove this by contrapositive. In other words, prove that for any integers x and y, if $7|x$ or $7|y$, then $7|xy$.

The instructor recommended proving this by cases, the first assuming $7|x$ and the second assuming $7|y$.

The instructor noted that proving just one of the cases is insufficient to prove the entire statement. Logically, however, I don't see why proving one statement of the disjunction does not suffice.

For example, the contrapositive of $P \implies (Q \wedge R)$ is $(\neg Q \vee \neg R) \implies \neg P$.

In this case P: $7 \nmid$ xy, Q: 7 $\nmid$ and R: $7 \nmid$ y.

So if either $\neg Q$ or $\neg R$ imply $\neg P$, to original statement is proven.

In regards to the proof by cases, I believe there are actually 4 cases:

  1. $7 | x$ and $7 \nmid y$
  2. $7 \nmid x$ and $7|y$
  3. $7 | x$ and $7|y$
  4. $7 \nmid x$ and $7\nmid y$

But since they are connected by a disjunction, proving case 1 or 2 should be sufficient.

To reiterate the question, why is my logical understanding of the contrapositive of this compound statement correct? And if so, why must both antecedents be proven when connected by a disjunction?


1 Answer 1


Note that in general:

$$(X \lor Y) \rightarrow Z \Leftrightarrow (X \rightarrow Z) \color{red}\land (Y \rightarrow Z)$$

Applied to your case:

$$(\neg Q \lor \neg R) \rightarrow \neg P \Leftrightarrow (\neg Q \rightarrow \neg P) \land (\neg R \rightarrow \neg P)$$

So, you need to show both $\neg Q \rightarrow \neg P$ and $\neg R \rightarrow \neg P$ in order to show $(\neg Q \lor \neg R) \rightarrow \neg P$

If you only show one case (say, the '$\neg Q$' case), then you have shown $\neg Q \rightarrow \neg P$, which is not enough. Indeed, the contrapositive of that is $P \rightarrow Q$ ... which is not what you want, nor does it imply what you want, because that is $P \rightarrow (Q \land R)$, which is a stronger statement.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .