1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook