On this page we prove the following theorem
stated by Euler in 1750 and proved by Lagrange in 1775. We use this
theorem on our page about Mersenne primes.

Theorem.

Let p = 3 (mod 4) be prime. 2p+1 is also prime if and
only if 2p+1 divides M_{p}.

Proof.

Suppose q = 2p+1 is prime. q = 7 (mod 8)
so 2 is a quadratic residue modulo q and it follows that there is
an integer n such that n^{2} = 2 (mod q).
This shows

2^{p} = 2^{(q-1)/2} = n^{q-1}
= 1 (mod q),

showing q divides M_{p}.
Conversely, let 2p+1 be a factor of M_{p}.
Suppose, for proof by contradiction, that 2p+1 is composite and let
q be its least prime factor. Then 2^{p} = 1
(mod q) and the order of 2 modulo q divides both p
and q-1, hence p divides q-1. This shows q > p
and it follows

(2p+1) + 1 > q^{2} > p^{2}

which is a contradiction since p > 2.

Notes

This means that if p = 3 (mod 4) and 2p+1 are both prime,
then either p is 3 or M_{p} is composite.

It is also the case that given p = 1 (mod 4) is prime; 2p+1 is also prime if
and only if 2p+1 divides 2^{p}+1 (see Lifchitz's page).