Proof of a result of Euler and Lagrange on Mersenne Divisors 
(From the Prime Pages' list of proofs)


Home
Search Site

Largest
The 5000
Top 20
Finding
How Many?
Mersenne

Glossary
Prime Curios!
Prime Lists

FAQ
e-mail list
Titans

Submit primes

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).
The Prime Pages
Another prime page by Chris K. Caldwell <caldwell@utm.edu>