On Mersenne Numbers (number theory)

[louiswins]

Homework Statement

For a positive integer k, the number M_k = 2^k - 1 is called the kth Mersenne number. Let p be an odd prime, and let q be a prime that divides M_p.

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

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

Homework Equations

Nothing beyond the above.

The Attempt at a Solution

OK, I don't really know how to proceed. Working backwards, iff \gcd(q-1, p) = q, the given equation says

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

but I don't know how to show this. We just have that q \mid 2^p-1 and q \mid 2^{q-1}-1.

 

[Joffan]

There are only two possible values for gcd(n,p) when p is prime: 1 and p.

 

[louiswins]

There are only two possible values for gcd(n,p) when p is prime: 1 and p.

Oh my goodness, you are absolutely right. I don't know how I overlooked this!