# Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0$ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$.

So far I have: Suppose it is false that $x$ does not divide $y$ and $x$ does not divide $z$. Then by De Morgan's law, $x|y$ or $x|z$.

Suppose $x|y$ then $y = xk$, where $k$ is an integer.

I'm a bit unsure of where to go from here.

• Made a small error, edited! – Wilson Jun 19 '14 at 20:00

If $x\mid y$, then $y = kx$ for some integer $k$.
If $x \mid z$, then $z = jx$ for some integer $j$.
$$\implies yz = (kz)x \lor yz=(jy)x \implies x\mid yz$$ by the definition of divisibility.
• That's what I proved: If we want to prove $p\rightarrow q$, and we assume $\lnot q$, then we want to prove $\lnot p$. In this case, the negation of "x does not divide yz" is "x divides yz". Proving $\lnot q \rightarrow \lnot p$ IS proving $p \rightarrow q.$ – amWhy Jun 19 '14 at 20:03
If $(x|y)\lor(x|z)$ then $(y=kx)\lor(z=k'x)$ so $(yz=(kz)x)\lor(yz=(k'y)x)$ so in the both cases $x|yz$. The contrapositive is the desired result.