If 2ⁿ-1 is prime, then so is n

By Chris Caldwell

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.

Proof.

Let r and s be positive integers, then the polynomial x^rs-1 is x^s-1 times 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 2^s-1). ∎

Notice that we can say more: suppose n > 1. Since x-1 divides xⁿ-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 a is 2 and n is prime.

Usually the first step in factoring numbers of the forms aⁿ-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.