5
$\begingroup$

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

Thanks...

1 Answers 1

4

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.

  • 0
    @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.2012-05-30