Euler and Lagrange on Mersenne Divisors
By Chris Caldwell
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. Then 2p+1 is also prime if and only if 2p+1 divides M_{p}.
 Proof.

First suppose q = 2p+1 is prime, then 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^{(q1)/2} ≡ n^{q1} ≡ 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 q1, hence p divides q1. 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).