Verified answer

b)

Given two positive integers x and y, the following always holds GCD(x,y) = GCD(x,y-x)

To see why notice that any positive integer that divides x and y must also divide y-x.

So GCD(x,y) divides both x and y-x and therefore GCD(x,y) <= GCD(x,y-x)

Similarly any positive integer that divides x and y-x must divide x+(y-x) = y, which implies GCD(x,y-x)<= GCD(x,y). Consequently we must have GCD(x,y) = GCD(x,y-x).

Using this fact we have GCD(M_n,M_m) = GCD(M_m,M_n-M_m)

but M_n-M_m = 2^n - 2^m = 2^m (2^(n-m) - 1) = 2^m M_(n-m) = (M_m + 1)M_(n-m)

So GCD(M_n,M_m) = GCD(M_m, M_m M_(n-m)+M_(n-m))

Keep subtracting M_m from M_m M_(n-m)+M_(n-m) to get

GCD(M_m, M_m M_(n-m)+M_(n-m))

= GCD(M_m, M_m (M_(n-m)-1)+M_(n-m))

= GCD(M_m, M_m (M_(n-m)-2)+M_(n-m))

...

= GCD(M_m, M_(n-m))

So GCD(M_n,M_m) = GCD(M_m,M_(n-m))

Use this fact repeatedly to show

GCD(M_m,M_n)

= GCD(M_m,M_(n-m))

= GCD(M_m,M_(n-2m))

= GCD(M_m,M_(n-3m))

...

= GCD(M_m,M_r)

as required.

c)

We can use the result from part (b) to reduce the indices just as in the Euclidean algorithm.

i.e.

GCD(M_n,M_m)

= GCD(M_m,M_r)

= GCD(M_r, M_s) where s is the remainder of m divided by r

= GCD(M_s, M_t) where t is the remainder of r divided by s

... etc.

The indices are strictly decreasing and eventually one of them must go to 0, so we will have

GCD(M_n, M_m) = GCD(M_f, M_0) = GCD(M_f, 0) = M_f

Also we know that GCD(n,m) = GCD(m,r) (because r is n subtracted by m a few tmes, and we showed GCD(x,y) = GCD(x,y-x) in part (b)). Similarly we know that

GCD(m,r) = GCD(r,s) = GCD(s,t) = .... = GCD(f,0) = f

So GCD(M_n,M_m) = M_(GCD(m.n)).