Question about gcd and Mersene Numbers

**~Death~** · Jun22-09, 03:45 AM

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

**~Death~** · Jun22-09, 03:57 AM

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

**~Death~** · Jun22-09, 05:04 AM

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)

**Jarle** · Jun22-09, 08:11 AM

$LaTeX Code: 2^{da}-1=(2^d-1)(1+2^d+...+2^{d(a-1)})$

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

Now, suppose $LaTeX Code: k|1+2^{d}+..+2^{d(a-1)}=A$ and $LaTeX Code: k|1+2^d+...+2^{d(b-1)}=B$ . If you invent some new notation by linearly combining

and

and use the fact that

is odd you can conclude that

. It takes some time so I wont post it here. Just a tip.