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!