We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
According to the definition of Greatest Common Divisior, if m is any integer, then gcd(a + m * b, b) = gcd(a, b).
(In this particular problem m = 1 or m = -1 in each step.) Therefore, the gcd of
(a + b, b), (a, a + b), (a - b, b) and (a, a - b)
will be the same as the gcd of (a, b). Therefore, in order to move to the target point, the gcd of the target point should be equal to the gcd of the starting point.
Possible Path
You are viewing a single comment's thread. Return to all comments →
According to the definition of Greatest Common Divisior, if m is any integer, then
gcd(a + m * b, b) = gcd(a, b). (In this particular problem m = 1 or m = -1 in each step.) Therefore, the gcd of (a + b, b), (a, a + b), (a - b, b) and (a, a - b) will be the same as the gcd of (a, b). Therefore, in order to move to the target point, the gcd of the target point should be equal to the gcd of the starting point.