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!

GCD and Relative Primes

  1. Jul 19, 2011 #1
    I'm not exactly sure how to prove or disprove this statement. Just by looking at the c, I'd say it's not true, but I'm not sure how to show it either way.

    If (a,b) = 1 and (a,c) = 1, then (ac,b) = 1.

    http://i111.photobucket.com/albums/n149/camarolt4z28/IMG_20110719_192439-1.jpg?t=1311127377 [Broken]
     
    Last edited by a moderator: May 5, 2017
  2. jcsd
  3. Jul 19, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If you think it's not true, and it's not. Then just give a counterexample.
     
    Last edited by a moderator: May 5, 2017
  4. Jul 19, 2011 #3
    I thought about that. However, how do I quickly find two relative primes? Just pick them? Let me try 3 and 7. Their only common divisor is 1.
     
  5. Jul 19, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Sure, try them. (3,7)=1. So let a=3 and b=7. Now pick c.
     
  6. Jul 19, 2011 #5

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Consider some of the possible prime factorizations of a, b, and c which are consistent with (a,b) = 1 and (a,c) = 1, and not consistent with (ac,b) = 1, if that's possible.

    If (ac,b) > 1 , and (a,b) = 1 , then what's true about (b,c) ?
     
  7. Jul 19, 2011 #6
    In trying to work a counterexample, it would appear that b = c, from your two given statements.
     
  8. Jul 19, 2011 #7

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Not necessarily.
     
  9. Jul 19, 2011 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    b=c works, if they are relatively prime to a. That's enough to disprove the statement. But as SammyS said they don't have to be equal to provide a counterexample.
     
  10. Jul 19, 2011 #9
    (3,7) = 1

    1 = am + bn
    1 = (3)(-2) + (7)(1)

    a = 3
    b = 7
    m = -2
    n = 1

    (3,5) = 1

    a = 3
    c = 5
    1 = am + cn
    1 = (3)(-2) + (5)(1) = -1

    Of course, that's not true. Do the m and n have to be the same?
     
  11. Jul 19, 2011 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No, not at all. (a,b)=1 if am+bn=1 for SOME integers m and n. (a,c)=1 if ak+bl=1 for SOME integers k and l. Of course, m and n don't have to be the same as k and l. I'd suggest you just concentrate on creating a counterexample for now. Use the b=c case, then try and find one where b is not equal to c.
     
  12. Jul 19, 2011 #11
    Well, that's the first important point I wasn't sure about.

    If I use (3,7) and (3,7), with

    m = -2
    n = 1

    k = 5
    l = -2

    1 = acp + bq
    1 = (3)(7)(p) + (7)(q)

    Of course, that will never work because the two terms are multiples of 7, right?
     
  13. Jul 19, 2011 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Right. But you are maybe getting carried away with how important the am+bn=1 condition is. You don't need it for this proof. gcd(3,7)=1 because they have no common divisor except 1, since they are both different primes. You know this before you even find the m and n. If you put a=3, b=7 and c=7 then gcd(a,b)=1 gcd(a,c)=1 and gcd(ac,b)=gcd(21,7). That's not 1, is it? That's really all you need to do.
     
  14. Jul 19, 2011 #13
    Oh. Sometimes I get bogged by the thought of needing to use the general cases.

    I wrote down (7,9) and (7,3). That should be another counterexample.

    (21,9) = 3
     
  15. Jul 19, 2011 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That also works. No need for the relation 1=am+bn, right?
     
  16. Jul 19, 2011 #15
    Not this time. Sometimes, you need it, though.

    I have one more homework problem.

    If b is greater than 0 and a = bq + r, prove that (a,b) = (b,r).

    I'll give it a shot in a few minutes.
     
  17. Jul 19, 2011 #16

    Mark44

    Staff: Mentor

    It might be helpful to write down a few examples using actual numbers, to help you better understand the symbols. The examples can't be used as a proof, but they can be useful for getting your head around the problem.

    For example, 35 = 5*6 + 5. Here (a, b) = (35, 5) = 5, and (b, r) = (5, 5) = 5.
    For another, 13 = 2*5 + 3. Here (a, b) = (13, 2) = 1, and (b, r) = (2, 3) = 1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: GCD and Relative Primes
  1. Relatively prime (Replies: 11)

Loading...