找到一对可以使用4个操作到达另一对的整数

Question

给定一对整数(例如(x,y)).我想找到是否有可能一次只使用下面提到的4个操作将它们转换为另一对整数.操作如下:

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

例如.(4,2)可以通过以下操作转换为(2,6):

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

其中(2,2)不能转换为(4,4).答案应该是肯定或否定.

Answer 1

声明:当且仅当,(x, y)才能达到.(z, w)gcd(x, y) = gcd(z, w)

证明:(必要)gcd(x, y) = gcd(x, x + y) = gcd(x + y, y) = gcd(x - y, y) = gcd(x, x - y).(足够)可达性是对称的.运行欧几里德算法以达到(gcd(x, y), 0)从(x, y).