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 (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² > p²

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).