A proof that if 2n-1 is prime, then so is n 
(From the Prime Pages' list of proofs)

Search Site

The 5000
Top 20
How Many?

Prime Curios!
Prime Lists

e-mail list

Submit primes

The goal of this short "footnote" is to prove the following theorem used in the discussion of Mersenne primes.
If for some positive integer n, 2n-1 is prime, then so is n.
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.
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>