1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 5, 2007 #1
    1. The problem statement, all variables and given/known data

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



    2. Relevant equations

    Division! LOL...



    3. 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: Apr 5, 2007
  2. jcsd
  3. Apr 5, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Stop thinking about writing proofs. Just think about the statement. Write down a few examples, try to see what is happening.
     
  4. Apr 5, 2007 #3
    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?
     
  5. Apr 5, 2007 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    a is supposed to divide bc. How does 42 divide 21?
     
  6. Apr 5, 2007 #5
    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?
     
  7. Apr 5, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Apr 5, 2007 #7
    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.
     
  9. Apr 5, 2007 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Sigh.
    Every number divides itself. What if a number is not prime?
     
  10. Apr 5, 2007 #9
    A number is not prime when it can be divided by a number other than itself or one.
     
  11. Apr 5, 2007 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    So 6, say, divides 6. 6 isn't prime, so how can you write 6 as the product of 2 smaller numbers?
     
  12. Apr 5, 2007 #11
    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.
     
  13. Apr 5, 2007 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  14. Apr 5, 2007 #13
    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?
     
  15. Apr 5, 2007 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?