Prove Divisibility: Proving & Disproving

[knowLittle]

Homework Statement

a.) Prove: If an integer $a$ does not divide $bc$, then $a$ does not divide $b$ and $a$ does not divide $c$.
b.) State and either prove or disprove the converse of the above statement.

The Attempt at a Solution

a.) Proof by contrapositive
$a|c \vee a|b \implies a|bc \\ c=ak \vee b =ap$Now, we multiply them by each other and
$bc = a(kap) , kap \in \mathbb{Z}$

So, it follows and the original statement in a is proved.

b.) Now, the converse.
$a\not|c \wedge a\not |b \implies a \not | bc$Can I say?
$a\not|c \wedge a\not |b$
$c \not =ak \\ b \not = ap$Multiply
$cb \not = a(kap)$ then
$a \not | cb, kap \in \mathbb{Z}$

 

[Curious3141]

Homework Statement

a.) Prove: If an integer $a$ does not divide $bc$, then $a$ does not divide $b$ and $a$ does not divide $c$.
b.) State and either prove or disprove the converse of the above statement.

The Attempt at a Solution

a.) Proof by contrapositive
$a|c \vee a|b \implies a|bc$

This is the correct contrapositive of the proposition you are asked to prove. But you shouldn't just state it like this (because it sounds like you're assuming it at the outset). You can preface the statement by: "We therefore need to show that the contrapositive holds, i.e...". Then the proof follows.

$c=ak \vee b =ap$

Now, we multiply them by each other and
$bc = a(kap) , kap \in \mathbb{Z}$

This is wrong. Remember that you are using a logical disjunction (OR) denoted by $\vee$ in your contrapositive statement. That means that either the first condition OR the second (or both) are true. But it clearly may not be that BOTH are true simultaneously, which is what you're assuming by just multiplying out the expressions.

Why not start with the first condition $c=ak$, and just multiply that by $b$ to get $bc = akb = (a).(kb)$? Then repeat the same with the other condition $b=ap$ and multiply by $c$. Isn't that sufficient to prove the contrapositive, and therefore the original proposition?

b.) Now, the converse.
$a\not|c \wedge a\not |b \implies a \not | bc$Can I say?
$a\not|c \wedge a\not |b$
$c \not =ak \\ b \not = ap$Multiply
$cb \not = a(kap)$ then
$a \not | cb, kap \in \mathbb{Z}$

First of all, is the converse true or false? Hint: consider $a, b$ and $c$ to have just two prime factors each. Let's say $a = pq, b = qr, c = pr$, where $p,q,r$ are all distinct primes. Now think about the implications to the converse proposition.

 

[knowLittle]

Why not start with the first condition $c=ak$, and just multiply that by $b$ to get $bc = akb = (a).(kb)$? Then repeat the same with the other condition $b=ap$ and multiply by $c$. Isn't that sufficient to prove the contrapositive, and therefore the original proposition?

You are right, it is sufficient.

First of all, is the converse true or false? Hint: consider $a, b$ and $c$ to have just two prime factors each. Let's say $a = pq, b = qr, c = pr$, where $p,q,r$ are all distinct primes. Now think about the implications to the converse proposition.

Given your conditions, the converse technically would be true, since $(F \wedge F \implies F) \equiv T$
Am I right?

 

[Curious3141]

Given your conditions, the converse technically would be true, since $(F \wedge F \implies F) \equiv T$
Am I right?

Check again. Are you sure that $a \not | bc$?

 

[knowLittle]

Check again. Are you sure that $a \not | bc$?

Sorry, I got confused.
Let's see:

$a\not | c \wedge a\not | b \implies a \not |bc$
$pr \not = pqx \wedge qr \not = pqy \implies pq(r^2) \not = pqz$
$T \wedge T \implies F \equiv F$
So, the statement is false.

 

[Curious3141]

Sorry, I got confused.
Let's see:

$a\not | c \wedge a\not | b \implies a \not |bc$
$pr \not = pqx \wedge qr \not = pqy \implies pq(r^2) \not = pqz$
$T \wedge T \implies F \equiv F$
So, the statement is false.

Yes, the converse is false. I set those specific conditions so you would get a quick counter-example.

One general suggestion: please tidy up (simplify) your notation. I find it very difficult to understand your mathematical statements.

I would simply have written this as:

$a = pq, c = pr$

Now, $q \not | r \implies a \not | c$

Also, $a = pq, b = qr$

So $p \not | r \implies a \not | b$

Hence the first two conditions are jointly satisfied.

But $bc = (pq).r^2 = a.r^2$. Hence $a | bc$.

Therefore, $(a \not | b) \wedge (a \not | c) \not \Rightarrow (a \not | bc)$ and the converse is untrue.

A little wordy, but I think it's much clearer. Just a suggestion.

EDIT: I HATE LaTEX!

 

[knowLittle]

I like LaTEX. Why do you hate it?

 

[Curious3141]

I like LaTEX. Why do you hate it?

Difficulty in usage, many quirks, and some unpredictability (e.g. some tags not accepted, some symbols not appearing as they should, etc.). This is a topic for another thread and off topic, let's end it here.