[離散數學]

The frog is jumping through the cartesian coordinate systems in the
plane, starting from point (1,1) according to the following rules:
(i) from any point (a,b) the frog can jump to point (2a,b) or (a,2b);
(ii) if a > b, the frog can jump from (a,b) to (a-b,b) and if a < b, the frog can jump from (a,b) to (a,b-a) Can the frog arrive to the point: (a) (24,40), (b) (40,60), (c) (24,60), (d)(200,4)?





以下是 某位大大幫我解的




gcd(2a,b) = 2*gcd(a,b) or gcd(a,b) <==不太懂這一行 是如何來的

gcd(a,2b)同理

by Euclidean algorithm,

if a>b, gcd(a-b,b) = gcd(a,b)

if b>a, gcd(a,b-a) = gcd(a,b)

另外, gcd(1,1)=1

所以gcd(x,y)= 2^k, k=0,1,2,...

也就是說x與y的gcd會是2的冪次方的形式