# GCD of (a, a+2) = ?

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

1. ### BoypussYgame over.

Joined:
Jun 27, 2000
Messages:
51,953
0
Location:
Anyone know how to figure this one out?

2. ### Joe_CoolNever trust a woman or a government.Moderator

Joined:
Jun 30, 2003
Messages:
299,278
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_CoolNever trust a woman or a government.Moderator

Joined:
Jun 30, 2003
Messages:
299,278
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 ManProtect Your Digital Liberties

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

Joined:
Jun 30, 2003
Messages:
299,278