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: Gcd proofs check

  1. Sep 6, 2011 #1
    I was doing a couple proofs (since I'm new to them) involving gcds and I just would like you guys to check them to see if I actually proved anything. There are 2 separate problems here.

    For both problems, a,b,c are in Z with a and b not both zero.

    PROBLEM 1
    1. The problem statement, all variables and given/known data
    Prove [tex] (\frac{a}{(a,b)}, \frac{b}{(a,b)}) = 1 [/tex]

    3. The attempt at a solution
    With this proof I'm stuck. Let g = (a,b), thus g|a and g|b where a = lg and b = jg. Then, [tex] (\frac{a}{(a,b)}, \frac{b}{(a,b)}) [/tex] becomes [tex] (\frac{lg}{g}, \frac{jg}{g}) [/tex] which becomes [tex] (l , j) = 1. [/tex]

    And I don't know where to go from there.


    PROBLEM 2

    1. The problem statement, all variables and given/known data
    [tex] (a, b) = (a + cb, b) [/tex]

    3. The attempt at a solution
    Let (a, b) = d and (a + cb, b) = g, with d =/= g. Thus d|a and d|b, where a = ld and b = jd. Also g|a+cb and g|b, where b = gn. Since jd = b = gn, jd = gn, and since d|b and g|b, g=d, which is a contradiction, so (a,b) = (a+cb, b).
     
  2. jcsd
  3. Sep 6, 2011 #2
    Well, assume that d divides l and j. Prove that d=1.

    How does it follow from d|b and g|b that g=d?
     
  4. Sep 6, 2011 #3
    I know, I've tried that but I don't see how I can prove d = 1, that's why I'm stuck :)



    I actually made a huge mistake in that reasoning. Here it goes:

    Let (a, b) = d and (a + cb, b) = g, with d =/= g. Thus d|a and d|b, where a = ld and b = jd. Also g|a+cb and g|b, where b = gy.

    g= r(a+cb)+nb = ar + cbr + nb = ldr + cjdr + njd = d(l + cj + nj). Thus, g|d.

    Now, since g|a+cb, g|a and g|cb, right, since if g divides the sum, it also divides its individual parts? Let a = gx.

    d = ma + nb = mgx + nyg = g(mx + ny). Thus d|g. Since d|g and g|d, d=g.
     
  5. Sep 6, 2011 #4
    Well, if d divides l and j, then d divides a and b. Thus...

    This looks ok!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook