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!

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