GCD of (a, a+2) = ?

Discussion in 'OT Technology' started by BoypussY, Feb 8, 2006.

  1. BoypussY

    BoypussY game over.

    Joined:
    Jun 27, 2000
    Messages:
    51,953
    Likes Received:
    0
    Location:
    IN YOUR HEAD
    Anyone know how to figure this one out?
     
  2. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,278
    Likes Received:
    555
    If c is a common factor of two different numbers, that means the numbers can be written as a*c and b*c, and their difference is |a-b|*c. Therefore, the closest they can be (assuming a != b) is when |a-b|=1, making the difference 1*c = c.

    In other words, if GCF(a,b) = c, |a-b| >= c.

    So... Since 2 divides all even numbers, and no odd numbers,
    If a is even, a+2 is also even, and GCF(a,a+2) = 2.
    If a is odd, GCF(a,a+2) = 1.
     
  3. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,278
    Likes Received:
    555
    Alternatively, you could find the answer with one iteration of the euclidean algorithm:

    where a > b GCD(a,b) =
    1) GCD(b,c) where c is the remainder to a/b;
    OR
    2) b if the remainder is 0.

    So: if a>2:
    GCD(a,a+2)
    (a+2)/a = 1r2
    GCD(a,a+2) = GCD(a+2,2) = 1 if a+2 is odd, 2 if a+2 is even.

    if a=2:
    GCD(a,a+2)
    (a+2)/a = 4/2 = 2r0
    GCD(2,4) = 2

    if a=1:
    GCD(a,a+2)
    (a+2)/a = 3/1 = 3r0
    GCD(1,3) = 1
     
  4. Penguin Man

    Penguin Man Protect Your Digital Liberties

    Joined:
    Apr 27, 2002
    Messages:
    21,696
    Likes Received:
    0
    Location:
    Edmonton, AB
    Yeah, that's how I would have done it. Also what they're probably expecting on an assignment ;-).
     
  5. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,278
    Likes Received:
    555
    Probably. Too bad he didn't post more information on what he was looking for. :hs:
     

Share This Page