If a divides bc, must a divide b or a divide c?

[VinnyCee]

Homework Statement

Prove or disprove that if a|bc, where a, b, and c are positive integers, then a|b or a|c.

Homework Equations

Division! LOL...

The Attempt at a Solution

Try a proof by contradiction.

Suppose that a|b and a|c are both NOT true. Then... what?

I really, really, really super suck at proofs.

 

[matt grime]

Stop thinking about writing proofs. Just think about the statement. Write down a few examples, try to see what is happening.

 

[VinnyCee]

Let's try a = 42, b = 3, c = 7.

$$\frac{a}{bc}\,=\,\frac{42}{21}\,=\,2\,\longrightarrow\,a|bc$$

$$\frac{a}{b}\,=\,\frac{42}{3}\,=\,14\,\longrightarrow\,a|b$$

$$\frac{a}{c}\,=\,\frac{42}{7}\,=\,6\,\longrightarrow\,a|c$$

I don't think that there is a way to choose a, b and c such that a|b or a|c are not true. But how do I "show" such?

 

[matt grime]

a is supposed to divide bc. How does 42 divide 21?

 

[VinnyCee]

Let's try a = 42, b = 3, c = 7.

$$\frac{bc}{a}\,=\,\frac{21}{42}\,=\,0.5\,\longrightarrow\,a|bc\,not\,true$$

$$\frac{b}{a}\,=\,\frac{3}{42}\,=\,0.071\,\longrightarrow\,a|b\,not\,true$$

$$\frac{c}{a}\,=\,\frac{7}{42}\,=\,0.167\,\longrightarrow\,a|c\,not\,true$$
Let's try different numbers...

a = 7, b = 3, c = 14, bc = 42

$$\frac{bc}{a}\,=\,\frac{42}{7}\,=\,6\,\longrightarrow\,a|bc\,is\,true$$

$$\frac{b}{a}\,=\,\frac{3}{7}\,=\,0.428\,\longrightarrow\,a|b\,is\,NOT\,true$$

$$\frac{c}{a}\,=\,\frac{14}{7}\,=\,2\,\longrightarrow\,a|c\,is\,true$$

This only "shows" for these exact values of a, b, and c. How do I show for all a, b, and c?

 

[matt grime]

So from one example you think it is true for all examples? try some more. if you just thnk about prime factorization, rather thatn actually putting numbers into a calculator, it becomes easy.

 

[VinnyCee]

Prime factorization?

Dividing by two until the number is no longer divisible by two to get a prime at the end?

I don't see how that applies to this proof though.

 

[matt grime]

Sigh.
Every number divides itself. What if a number is not prime?

 

[VinnyCee]

A number is not prime when it can be divided by a number other than itself or one.

 

[matt grime]

So 6, say, divides 6. 6 isn't prime, so how can you write 6 as the product of 2 smaller numbers?

 

[VinnyCee]

3 * 2 = 6, yes, it is not prime.

How does this help with the proof though? I just don't understand how I am supposed to use prime numbers to prove anything about divisibility.

 

[matt grime]

So 6 divides 2*3. Now, what does the question ask?

Prove or disprove:

if a divides bc then a divides b or b divides c.

Now do you see? And do you see why primes are important?

 

[VinnyCee]

I still don't get it!

a = 6, b = 2, c = 3, bc = 6

$$\frac{bc}{a}\,=\,\frac{6}{6}\,=\,1$$ <----- claim holds

$$\frac{b}{a}\,=\,\frac{2}{6}\,=\,\frac{1}{3}$$ <----- claim does NOT hold

$$\frac{c}{a}\,=\,\frac{3}{6}\,=\,\frac{1}{2}$$ <----- claim does NOT hold

I guess using this case, the claim is disproved?

 

[Dick]

Good! You have disproved the claim. If you want some more insight into what's going on think about what would happen if the claim were a|bc AND a is prime implies a|b or a|c. Then would the conclusion hold?