# Prove Divisibility

1. May 19, 2014

### knowLittle

1. The problem statement, all variables and given/known data
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.

3. 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}$

2. May 20, 2014

### Curious3141

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.

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?

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.

Last edited: May 20, 2014
3. May 20, 2014

### knowLittle

You are right, it is sufficient.

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

4. May 20, 2014

### Curious3141

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

5. May 20, 2014

### knowLittle

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.

6. May 20, 2014

### Curious3141

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!

Last edited: May 20, 2014
7. May 20, 2014

### knowLittle

I like LaTEX. Why do you hate it?

8. May 20, 2014

### Curious3141

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.