Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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
    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
    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
    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
    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
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook