Euler and Lagrange on Mersenne Divisors
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.
- Let p ≡ 3 (mod 4) be prime. Then 2p+1 is also prime if and only if 2p+1 divides Mp.
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 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.∎
- 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).