1
$\begingroup$

I am having difficulty with the following proof. A prime $p$ is said to be a Sophie Germain prime if $2p+1$ is also prime. It is known that if $p$ is a sophie Germain prime, then $2p+1$ is a factor of the Mersenne number $M_p$. For example, $23$ is a sophie Germain prime since $47$ is also prime, so 47 divides $M_{23}$ and thus $M_{23}$ is not a Mersenne prime.

Given the result that $(\frac{2}{47})=1$ (this is Legendre's symbol), prove that $47$ is indeed a factor of $M_{23}$.

I know Legendre's symbol means that $2^{23}\equiv1\mod 47 $ and that $M_{23}$ is of the form $2^{23}-1$. So can I say:

$2^{23}\equiv1\mod 47$

$2^{23}-1\equiv0\mod 47$

$M_{23}\equiv0\mod 47$ so $47$ is indeed a factor.

This question is worth a few marks so I can't help but feel it isn't as simple as this. Can anyone tell me where/if I may have gone wrong?

$\endgroup$
2
$\begingroup$

Let we consider the prime $p=47$. Is $2$ a quadratic residue $\!\!\pmod p$?
Of course, since $47$ is a number of the form $8k-1$. That ensures: $$ \left(\frac{2}{p}\right) \equiv 2^{\frac{p-1}{2}} \equiv +1\pmod{47} $$ hence $47$ is a divisor of $2^{23}-1$, since $2^{\frac{p-1}{2}}-1\equiv 0\pmod{47}$.


Consequence: if $q>3$ is a prime and $2q+1$ is a prime of the form $8k- 1$, $$2^q-1\text{ is not a prime}.$$

$\endgroup$
  • $\begingroup$ So does this mean my attempt is correct? $\endgroup$ – harry55 Feb 25 '17 at 19:34
  • $\begingroup$ @harry: sure, I just gave a clearer re-phrasing. $\endgroup$ – Jack D'Aurizio Feb 25 '17 at 19:36
  • $\begingroup$ @JackD'Aurizio Your last statement is true except for the (silly) counterexample $q = 3$. $\endgroup$ – Ravi Fernando Feb 25 '17 at 19:52
  • $\begingroup$ @RaviFernando: correct, now fixed. Thanks for pointing that out. $\endgroup$ – Jack D'Aurizio Feb 25 '17 at 20:23

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.