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 Mp.
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 n2 = 2 (mod q).
This shows
2p = 2(q-1)/2 = nq-1
= 1 (mod q),
showing q divides Mp.
Conversely, let 2p+1 be a factor of Mp.
Suppose, for proof by contradiction, that 2p+1 is composite and let
q be its least prime factor. Then 2p = 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 > q2 > p2
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 Mp 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 2p+1 (see Lifchitz's page).
