Home
Search Site
Largest
The 5000
Top 20
Finding
How Many?
Mersenne
Glossary
Prime Curios!
Prime Lists
FAQ
email list
Titans
Submit primes

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(r1)}
+ x^{s(r2)} + ... + 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 x1 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. 