# On Mersenne Numbers (number theory)

1. Mar 5, 2012

### louiswins

1. The problem statement, all variables and given/known data
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$.

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 $\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$.

2. Mar 5, 2012

### Joffan

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

3. Mar 5, 2012

### louiswins

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