Discussion in 'OT Technology' started by BoypussY, Feb 8, 2006.
Anyone know how to figure this one out?
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.
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;
2) b if the remainder is 0.
So: if 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.
(a+2)/a = 4/2 = 2r0
GCD(2,4) = 2
(a+2)/a = 3/1 = 3r0
GCD(1,3) = 1
Yeah, that's how I would have done it. Also what they're probably expecting on an assignment ;-).
Probably. Too bad he didn't post more information on what he was looking for.