Clever Geek Handbook

Find a pair of intermediate links that can be achieved for another pair using 4 operations

For a pair of integers (e.g. (x, y)). I want to find if it is possible to convert them to another pair of integers using only the 4 operations mentioned below at a time for any number of times. The operations are as follows:

(x,x+y)
or (x+y,y)
or (x-y,y)
or (x,x-y)

For example, (4,2) can be converted to (2,6) by doing the following:

(x-y,y) --- (2,2)
(x,x+y) --- (2,4)
(x,x+y) --- (2,6)

where as (2,2) cannot be converted to (4,4). The answer must be yes or no.

+3


source to share


1 answer


Requirement: (x, y)

can achieve (z, w)

if and only if gcd(x, y) = gcd(z, w)

.



Proof: (required) gcd(x, y) = gcd(x, x + y) = gcd(x + y, y) = gcd(x - y, y) = gcd(x, x - y)

. (sufficient) Reachability is symmetric. Run Euclid's algorithm to achieve (gcd(x, y), 0)

from (x, y)

.

+5


source






More articles:


All Articles