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!

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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Well, if d divides l and j, then d divides a and b. Thus...

    This looks ok!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Gcd proofs check
  1. GCD = 1 Proof (Replies: 2)

Loading...