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$?



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.

  • $\begingroup$ +1 Thanks so far. Any idea about 3.? $\endgroup$ – draks ... May 30 '12 at 21:35
  • $\begingroup$ @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. $\endgroup$ – André Nicolas May 30 '12 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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