# Question about gcd and Mersene Numbers

1. Jun 22, 2009

### ~Death~

Hi,

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

but im 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 alot where youre given some aribtrary function and asked to show something about the gcd ...are there any tips for how to do these?

Thanks

2. Jun 22, 2009

### ~Death~

so far ive 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

Last edited: Jun 22, 2009
3. Jun 22, 2009

### ~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)

4. Jun 22, 2009

### 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 wont post it here. Just a tip.