Question about gcd and Mersene Numbers

[~Death~]

Hi,

I've been going through an intro number theory book and trying to prove everything

but I am stuck on this one exercise

it says to show that gcd(M_e,M_f)=M_gcd(e,f) for all positive integers e and f

where M_n=2^n-1.

Is there a simple proof for this?

I see these questions a lot where youre given some aribtrary function and asked to show something about the gcd ...are there any tips for how to do these?

Thanks

 

[~Death~]

so far I've proved that if a|b then M_a|M_b using the identity x^k-1=(x-1)(x^(k-1)+...+1)

so I have now M_gcd(e,f)|M_e and M_gcd(e,f)|M_f

but I'm not sure how to show that it's actually the GREATEST common divisor

 

[~Death~]

Ok I think I proved it

if d|M_e and d|M_f then

d|xM_e+yM_f for ANY integers x,y and by properties of gcd there exists

integers x',y' such that x'M_e+y'M_f=gcd(M_e,M_f) so then d|gcd(M_e,M_f)

 

[disregardthat]

2^{da}-1=(2^d-1)(1+2^d+...+2^{d(a-1)})

The same applies for 2^{db}-1. So obviously \gcd(M_{ad},M_{bd}) \geq 2^d-1.

Now, suppose k|1+2^{d}+..+2^{d(a-1)}=A and k|1+2^d+...+2^{d(b-1)}=B. If you invent some new notation by linearly combining A and B and use the fact that k is odd you can conclude that k|1. It takes some time so I won't post it here. Just a tip.