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^{n}-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^{n}-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^{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^{n}-1
is prime, then 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^{n}-1. In this proof we just used the most basic
of such factorization rules, see [BLSTW88] for some
others.