2
$\begingroup$

This is the theorem I need to show: "Let $q$ be a prime of the form $4k+3$. If $2q+1$ is prime, then $2q+1$ divides $2^q−1$."

I need to show this to show that $2^{251} - 1$ is not a Mersenne Prime.

1 Answers 1

3

Since $p=2q+1$ is a prime of the form $8k+7$, it follows that $2$ is a quadratic residue of $p$. (Recall that $2$ is a quadratic residue of the odd prime $p$ iff $p$ is of the form $8k\pm 1$.)

Thus by Euler's Criterion, $2^{(p-1)/2}\equiv 1\pmod{p}$, and therefore $2^q\equiv 1\pmod{p}$. This says that $p$, that is, $2q+1$, divides $2^q-1$.

Note that $2q+1$ is a proper divisor of $2^q-1$ unless $2q+1=2^q-1$. That happens when $q=3$, but nowhere else, since for $q\gt 3$, $2q+1\lt 2^q-1$.