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

Prime Links
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>