- #1

louiswins

- 3

- 0

## Homework Statement

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].

## Homework Equations

Nothing beyond the above.

## 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].