Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about gcd and Mersene Numbers

  1. Jun 22, 2009 #1
    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. jcsd
  3. Jun 22, 2009 #2
    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
  4. Jun 22, 2009 #3
    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)
     
  5. Jun 22, 2009 #4

    disregardthat

    User Avatar
    Science Advisor

    [tex]2^{da}-1=(2^d-1)(1+2^d+...+2^{d(a-1)})[/tex]

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

    Now, suppose [tex]k|1+2^{d}+..+2^{d(a-1)}=A[/tex] and [tex]k|1+2^d+...+2^{d(b-1)}=B[/tex]. If you invent some new notation by linearly combining [tex] A [/tex] and [tex] B [/tex] and use the fact that [tex]k[/tex] is odd you can conclude that [tex]k|1[/tex]. It takes some time so I wont post it here. Just a tip.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Question about gcd and Mersene Numbers
Loading...