You are currently browsing the tag archive for the ‘fermat numbers’ tag.
Proofs from THE BOOK by Martin Aigner and Günter Ziegler begins by giving six proofs of the infinity of primes. We will go over the third proof. Before we go over this proof, lets cover some background.
— 1. Fermat Numbers —
Fermat numbers are defined by
so that and
. They are of great interest in many ways: for example, it was proved by Gauss that, if
, is a prime
, then a regular polygon of
sides can be inscribed in a circle by Euclidean methods. The property of the Fermat numbers which is relevant here is
We will prove this theorem later.
The first four Fermat numbers are prime, and Fermat conjectured that all were prime. Euler, however, found in 1732 that
is composite.
In 1880 Landry proved that
It is currently known that , is composite for
. Factoring Fermat numbers is extremely difficult as a result of their large size.
has
known factors with
remaining (where
denotes a composite number with
digits).
has
known factors with
remaining.
has no known factors but is composite. There are currently four Fermat numbers that are known to be composite, but for which no single factor is known:
and
. In all the other cases proved to be composite a factor is known. No prime
has been found beyond
, and it seems unlikely that any more will be found using current computational methods and hardware.
— 2. Infinitude of Primes Theorem —
We are now ready to prove Euclid’s Second Theorem, also called the Infinitude of Primes Theorem using the third proof in Proofs from THE BOOK.
from which our assertion follows immediately. Indeed, if is a divisor of, say,
and
, then
divides
, and hence
or
. But
is impossible since all Fermat numbers are odd.
To prove the recursion we use induction on . For
we have
and
. With induction we now conclude