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!

Abstract Algebra: GCD proof

  1. Sep 26, 2011 #1
    1. The problem statement, all variables and given/known data

    If (a,c) = 1 and (b,c) = 1, prove that (ab,c) = 1. Note that (x,y) refers to the greatest common divisor between x and y.

    2. The attempt at a solution

    There is a theorem that says since (a,c) = 1, there exist integers u and v such that au + cv = 1. Likewise, there also exist integers p and q such that bp + cq = 1. How though, could that be tied to the proof's conclusion, that there exist integers m and n such that (ab)m + cn = 1? Thanks all!
     
  2. jcsd
  3. Sep 26, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    OK, let's do this from the definitions. Let p be a prime such that p divides ab and c. Can you reach a contradiction?
     
  4. Sep 26, 2011 #3
    Maybe, if p divides ab and c, then there is an x and y such that px = ab and py = c. Now substituting into au + cv = 1 gives (px/b)u + (py)v = p(xu/b + yv) = 1. If (xu/b + yv) is an integer, is this a contradiction?
     
  5. Sep 26, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    If p divides ab, can you show that p divides either a or b?
     
  6. Sep 26, 2011 #5
    I think so; if px = ab, then p(x/b) = a, meaning p divides a?
     
  7. Sep 26, 2011 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Not necessarily as you don't know that x/b is an integer.
     
  8. Sep 26, 2011 #7
    Ah! Okay, if py = c, then since au + cv = 1, substituting gives au + (py)v = au + p(yv) = 1, which means (a,p) = 1. It could be done similarly to show (b,p) = 1. Is this correct?
     
  9. Sep 26, 2011 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, this is already correct.
     
  10. Sep 26, 2011 #9
    Sorry, what do you mean? Do you mean to say that this is the end of the proof?
     
  11. Sep 26, 2011 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    No, I'm saying that what you done is correct.
     
  12. Sep 26, 2011 #11
    Okay, so I assume from there it must be true that p cannot divide ab, thus a contradiction. But how would you suggest writing this out in a rigorous manner?
     
  13. Oct 3, 2011 #12
    Ah, this works:

    ax + cy = 1 (1)

    bw + cz = 1 (2)

    Multiplying (2) by 'a' gives

    abw + cz = a (3)

    and substituting (3) into (1) gives

    (abw + cz)x + cy = ab(w) + c(azx + y) = 1

    meaning (ab,c) = 1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Abstract Algebra: GCD proof
  1. Algebra: GCD Proof (Replies: 2)

Loading...