Prove that the following proposition is true.

Question

Let a ∈ Z and let b ∈ Z. If n does not divide ab then n does not divide a and n does not divide b.

I am currently studying discrete math and I am unsure of how to format this proof in such a way to get my point across. If anyone could write it out for me that would be very appreciated! Thank you in advance.

Answer 1

We can prove that the proposition is true by proceeding by “reductio ad absurdum” that is the form of argument that attempts to establish a claim by showing that the opposite scenario would lead to absurdity or contradiction.

If $n$ divided $a$ or $b$, then there would exist $h\in\mathbb{Z}$ such that

$a=h\cdot n$

or

$b=h\cdot n$

Therefore, it would follow that

$ab=hb\cdot n$

or

$ab=ha\cdot n$

So in any case, we would get that $n$ would divide $ab$, but it would lead to contradiction because a hypothesis says that $n$ does not divide $ab$.

Therefore it is not possible that $n$ divides $a$ or $b$ because it leads to absurdity. So we can claim that $n$ does not divide $a$ and $n$ does not divide $b$.

Answer 2

Hint: The contrapositive is easier to read and very easy to prove:

If $n$ divides $a$ or $n$ divides $b$, then $n$ divides $ab$.

The original statement is of the form $$\operatorname{not} C \implies (\operatorname{not} A) \text{ and } (\operatorname{not} B)$$ The contrapositive is then of the simpler form $$A \text{ or } B \implies C$$