1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

On Mersenne Numbers (number theory)

  1. Mar 5, 2012 #1
    1. The problem statement, all variables and given/known data
    For a positive integer k, the number [itex]M_k = 2^k - 1[/itex] is called the kth Mersenne number. Let p be an odd prime, and let q be a prime that divides [itex]M_p[/itex].

    a. Explain why you know that q divides [itex]2^{q-1}-1[/itex].
    I have done this already using Euler's theorem, since q prime implies [itex]\varphi(q) = q-1[/itex].

    Here is the part that I'm having trouble with:
    b. Given that [itex]\gcd(2^{q-1}-1, 2^p-1) = 2^{\gcd(q-1,p)} - 1[/itex], show that [itex]\gcd(q-1, p) = p[/itex].

    2. Relevant equations
    Nothing beyond the above.

    3. The attempt at a solution
    OK, I don't really know how to proceed. Working backwards, iff [itex]\gcd(q-1, p) = q[/itex], the given equation says

    [itex]\gcd(2^p-1, 2^{q-1}-1) = 2^p-1[/itex], so
    [itex]2^p-1 \mid 2^{q-1}-1[/itex],

    but I don't know how to show this. We just have that [itex]q \mid 2^p-1[/itex] and [itex]q \mid 2^{q-1}-1[/itex].
     
  2. jcsd
  3. Mar 5, 2012 #2
    There are only two possible values for gcd(n,p) when p is prime: 1 and p.
     
  4. Mar 5, 2012 #3
    Oh my goodness, you are absolutely right. I don't know how I overlooked this! :blushing:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: On Mersenne Numbers (number theory)
  1. Mersenne numbers (Replies: 10)

  2. Number Theory (Replies: 11)

  3. Number theory (Replies: 5)

Loading...