# Using Legendre's symbol to prove that $47$ is a factor of the Mersenne number, $M_{23}$

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?

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}.$$
• @JackD'Aurizio Your last statement is true except for the (silly) counterexample $q = 3$. – Ravi Fernando Feb 25 '17 at 19:52