1. Limited time only! Sign up for a free 30min personal 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!

Greatest common divisor

  1. Sep 2, 2009 #1
    1. The problem statement, all variables and given/known data
    if (a,c)=1 and (b,c)=1 prove that (ab,c)=1


    2. Relevant equations

    I know that (a,c)=1 says that au+cv=1 and bs+ct=1 prove abq+cr=1


    3. The attempt at a solution

    I set au+cv=bs+ct now I don't know what to do
     
  2. jcsd
  3. Sep 2, 2009 #2
    do you know the theorem that if d|ab, then d|a or d|b?
     
  4. Sep 2, 2009 #3
    Yes I did learn that, but how do I use that?
     
  5. Sep 2, 2009 #4
    So, I should prove by contradiction. If some other number divides ab then it must divide a or b but it does not divide either so it (ab,c) must = 1
     
  6. Sep 2, 2009 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's false. 6|(3*4) but 6 doesn't divide 3 or 4. You had better say the word 'prime' at some point.
     
  7. Sep 2, 2009 #6
    So if I let x equal a prime number greater than 1 I can prove by contradiction that it either divides a or b and since it doesn't there is the contradiction
     
  8. Sep 2, 2009 #7
    Wait... x is a prime number greater than 1 that divides c
     
  9. Sep 2, 2009 #8
    You're right. Thanks for the correction
     
  10. Sep 2, 2009 #9
    Thanks
     
  11. Sep 2, 2009 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Slow down. Can you state your reasoning in complete sentences? (a,c)=1 means a and c have no common prime divisors. Now continue.
     
  12. Sep 2, 2009 #11
    you don't need to specify 'greater than 1' because 1 isn't prime.


    so if d|(ab, c), then there exists some prime p such that p|ab.
     
  13. Sep 2, 2009 #12
    Let x = a prime number greater than 1 that divides c. Assume (ab,c)=x. Based on the theorem we know that x|a or x|b. However, based on the given that (a,c)=1 and (b,c)=1, we know that x does not divide a and x does not divide b. Hence there is a contradiction and x cannot be a prime number greater than 1. Since we know there is no prime number less than 1, x must equal 1
     
  14. Sep 2, 2009 #13
    that doesn't look quite right. strike the first sentence and let p|x where p is prime. Go from there. It's mostly good though. The problem is that (ab, c) might not be prime.
     
  15. Sep 2, 2009 #14
    Did not see your next post, but that is right, so I can simplify by answer to x cannot be a prime number that divides c, so x must equal 1
     
  16. Sep 2, 2009 #15
    A philospher: my x equals a prime number that divides c.
     
  17. Sep 2, 2009 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Why are you rushing this? Think about it. You can't assume BOTH x|c AND (ab,c)=x without justifying it. Look, start from this: If (ab,c) is not 1, then let x be a prime that divides (ab,c). Go from there. SLOWLY.
     
  18. Sep 2, 2009 #17
    Ok, but can I leave x as a prime number that divides c but is simply a common divisor not necessarily the greatest common divisor. Then I still can say it does not divide a or b so must be 1
     
  19. Sep 2, 2009 #18
    Ok let me start again.
     
  20. Sep 2, 2009 #19
    Yes you can. By definition. What can't be assumed is that (ab, c)=x and that x is prime.
     
  21. Sep 2, 2009 #20
    Ok: Let x be a prime number such that divides (ab,c). Now this means that x must divide c and must divide either a or b. Now I can say here is the contradiction, we know x does not divide a or b so x cannot divide (ab,c). Therefore x must equal 1
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Greatest common divisor
Loading...