# If 2^{n}-1 is prime, then so is *n*

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*, 2-1 is prime, then so is^{n}*n*. - Proof.
- Let
*r*and*s*be positive integers, then the polynomial*x*-1 is^{rs}*x*-1 times^{s}*x*^{s(r-1)}+*x*^{s(r-2)}+ ... +*x*^{s}+ 1. So if*n*is composite (say*r*^{.}*s*with 1 <*s*<*n*), then 2-1 is also composite (because it is divisible by^{n}*2*-1). ∎^{s}

Notice that we can say more: suppose *n* > 1. Since *x*-1 divides *x ^{n}*-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*a*-1 is prime, then^{n}*a*is 2 and*n*is prime.

Usually the first step in factoring numbers of the forms *a ^{n}*-1
(where

*a*and

*n*are positive integers) is to factor the polynomial

*x*-1. In this proof we just used the most basic of such factorization rules, see [BLSTW88] for some others.

^{n}Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.