Home
Search Site
Largest
The 5000
Top 20
Finding
How Many?
Mersenne
Glossary
Prime Curios!
Prime Lists
FAQ
email 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 M_{p}.
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 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).
