Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The wiki page on Mersenne Primes gives 8 theorems about Mersenne primes. My question relates to number 4. and 7.:

4.If $p$ is an odd prime, then any prime $q$ that divides $2^p-1$ must be congruent to $\pm 1 (\bmod 8)$.

7.If $p$ and $2p+1$ are both prime (meaning that $p$ is a Sophie Germain prime), and $p$ is congruent to $3 (\bmod 4)$, then $2p+1$ divides $2^p − 1$.

I have 3 questions:

  1. Isn't this equivalent, since from 7. we get $2p+1=8n +7$ which is $- 1 (\bmod 8)$? Ok, I see that 7. is more stringent, since 4. also allows $1$ as divisor. If this is answer to 1., my next question is

  2. How does the property of $p$ and $2p+1$ both prime force that $2p+1$ divides $2^p − 1$?

  3. Is this extendable? Can a Cunningham chain help to find more divisors of $2^p − 1$?


share|cite|improve this question
up vote 3 down vote accepted

For the second question: Note that $2p+1$ is of the form $8k+7$. So $2$ is a quadratic residue of $2p+1$. Thus $2\equiv a^2\pmod{2p+1}$ for some $a$. But then $2^p\equiv a^{2p}\equiv 1\pmod{2p+1}$ by Fermat's Theorem.

Assertion $4$ just puts restrictions on the form of divisors, without asserting that non-trivial divisors exist. Assertion $7$ says that a very specific number is a divisor, albeit in a very restricted setting (Sophie Germain primes). For example, it enables us to conclude, without any trial divisions, that $2^{11}-1$ is not prime, and that $2^{23}-1$ is not prime.

share|cite|improve this answer
+1 Thanks so far. Any idea about 3.? – draks ... May 30 '12 at 21:35
@draks: Unfortunately no ideas about how to use a Cunningham Chain. We have that $47$ is the end of the medium length chain $47$, $23$, $11$, $5$, but the only small factors that I can find come from the Sophie Germain prime criterion. – André Nicolas May 30 '12 at 21:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.