A proof that if 2n-1 is prime, then so is n 
(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

The goal of this short "footnote" is to prove the following theorem used in the discussion of Mersenne primes.
Theorem.
If for some positive integer n, 2n-1 is prime, then so is n.
Proof.
Let r and s be positive integers, then the polynomial xrs-1 is xs-1 times xs(r-1) + xs(r-2) + ... + xs + 1.  So if n is composite (say r.s with 1<s<n), then 2n-1 is also composite (because it is divisible by 2s-1).
Notice that we can say more: suppose n>1. Since x-1 divides xn-1, for the latter to be prime the former must be one. This gives the following.
Corollary.
Let a and n be integers greater than one.  If an-1 is prime, then a is 2 and n is prime.
Usually the first step in factoring numbers of the forms an-1 (where a and n are positive integers) is to factor the polynomial xn-1.  In this proof we just used the most basic of such factorization rules, see [BLSTW88] for some others.
The Prime Pages
Another prime page by Chris K. Caldwell <caldwell@utm.edu>