Prove or Disprove: if a | bc, then a|b or a|c

  • Thread starter VinnyCee
  • Start date
  • #1
489
0

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.
 
Last edited:

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
Stop thinking about writing proofs. Just think about the statement. Write down a few examples, try to see what is happening.
 
  • #3
489
0
Let's try a = 42, b = 3, c = 7.

[tex]\frac{a}{bc}\,=\,\frac{42}{21}\,=\,2\,\longrightarrow\,a|bc[/tex]

[tex]\frac{a}{b}\,=\,\frac{42}{3}\,=\,14\,\longrightarrow\,a|b[/tex]

[tex]\frac{a}{c}\,=\,\frac{42}{7}\,=\,6\,\longrightarrow\,a|c[/tex]

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?
 
  • #4
matt grime
Science Advisor
Homework Helper
9,395
3
a is supposed to divide bc. How does 42 divide 21?
 
  • #5
489
0
Let's try a = 42, b = 3, c = 7.

[tex]\frac{bc}{a}\,=\,\frac{21}{42}\,=\,0.5\,\longrightarrow\,a|bc\,not\,true[/tex]

[tex]\frac{b}{a}\,=\,\frac{3}{42}\,=\,0.071\,\longrightarrow\,a|b\,not\,true[/tex]

[tex]\frac{c}{a}\,=\,\frac{7}{42}\,=\,0.167\,\longrightarrow\,a|c\,not\,true[/tex]



Let's try different numbers...

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

[tex]\frac{bc}{a}\,=\,\frac{42}{7}\,=\,6\,\longrightarrow\,a|bc\,is\,true[/tex]

[tex]\frac{b}{a}\,=\,\frac{3}{7}\,=\,0.428\,\longrightarrow\,a|b\,is\,NOT\,true[/tex]

[tex]\frac{c}{a}\,=\,\frac{14}{7}\,=\,2\,\longrightarrow\,a|c\,is\,true[/tex]

This only "shows" for these exact values of a, b, and c. How do I show for all a, b, and c?
 
  • #6
matt grime
Science Advisor
Homework Helper
9,395
3
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.
 
  • #7
489
0
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.
 
  • #8
matt grime
Science Advisor
Homework Helper
9,395
3
Sigh.
Every number divides itself. What if a number is not prime?
 
  • #9
489
0
A number is not prime when it can be divided by a number other than itself or one.
 
  • #10
matt grime
Science Advisor
Homework Helper
9,395
3
So 6, say, divides 6. 6 isn't prime, so how can you write 6 as the product of 2 smaller numbers?
 
  • #11
489
0
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.
 
  • #12
matt grime
Science Advisor
Homework Helper
9,395
3
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?
 
  • #13
489
0
I still don't get it!

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

[tex]\frac{bc}{a}\,=\,\frac{6}{6}\,=\,1[/tex] <----- claim holds

[tex]\frac{b}{a}\,=\,\frac{2}{6}\,=\,\frac{1}{3}[/tex] <----- claim does NOT hold

[tex]\frac{c}{a}\,=\,\frac{3}{6}\,=\,\frac{1}{2}[/tex] <----- claim does NOT hold

I guess using this case, the claim is disproved?
 
  • #14
Dick
Science Advisor
Homework Helper
26,260
619
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?
 

Related Threads on Prove or Disprove: if a | bc, then a|b or a|c

Replies
3
Views
26K
Replies
6
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
2
Views
3K
Replies
12
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
Replies
1
Views
2K
Replies
1
Views
1K
Top