Results 1 to 2 of 2

Thread: GCD Proof

  1. #1
    Nov 2012

    GCD Proof

    if I have x and y be odd integers. Then 2gcd(x,y) = gcd(x+y,x-y). I am completely lost for what to do. I may be over think this but help would greatly be appreciated. This is what I have so far:

    Let d = gcd(x,y) and e = gcd(x+y, x-y). To prove that e = 2d it suffices to show that 2d|e and e|2d. To show that 2d|e we need to show that 2d|(x-y) and 2d|(x+y). Thus e = (x+y)s + (x-y)t and d = xk + yl and 2d = 2xk + 2yl. (x-y) with x and y being always odd will always return even so x-y = 2n and (x+y) with x and y being always odd will always return even so x-y = 2m for some s,t,k,l,n and m in Z. Thus,

    2n = (2xk + 2yl)z

    2n = 2xkz +2ylz

    n = xkz + ylz

    2m = (2xk + 2yl)z

    2m = 2xkz + 2ylz

    m = xkz+ylz

    But honestly I dont even know if this is right. I need help!! I have 2 others like this and have no clue where to go!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Feb 2013

    Re: GCD Proof

    First, we set d=gcd(x,y) and e=gcd(x+y,x-y)

    Now we will show that 2d<=e and that e<=2d. I would say that this is the most common way of proving equalities involving gcd.

    First, observe that since d|x and d|y, we have d|(x+y) and d|(x-y). Since x and y are both odd we also have 2|(x+y) and 2|(x-y). Once again, because x and y are both odd, we know that d is also odd and so it follows that 2d|x+y and 2d|x-y. Hence, 2d<=e.

    For the other direction, observe that since e|(x+y) and e|(x-y), we have e|(x+y+x-y) and e|(x+y-(x-y)). So, e|2x and e|2y. Since x and y are both odd, this implies that e<=2d.

    Therefore, 2d=e as desired.

    Hope this helps!

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [Abstract Algebra] Anyone care to proof-read a proof?
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Dec 4th 2012, 02:13 PM
  2. Replies: 15
    Last Post: Jun 8th 2011, 12:13 PM
  3. Replies: 5
    Last Post: Oct 19th 2010, 11:50 AM
  4. Replies: 0
    Last Post: Jun 29th 2010, 09:48 AM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: Apr 14th 2008, 05:07 PM

Search Tags

/mathhelpforum @mathhelpforum