Main Page | See live article | Alphabetical index

Fermat number

A Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form

where n is a nonnegative integer. The first eight Fermat numbers are

F0 = 21 + 1 = 3
F1 = 22 + 1 = 5
F2 = 24 + 1 = 17
F3 = 28 + 1 = 257
F4 = 216 + 1 = 65537
F5 = 232 + 1 = 4294967297
F6 = 264 + 1 = 18446744073709551617
F7 = 2128 + 1 = 340282366920938463463374607431768211457

If 2n + 1 is prime, it can be shown that n must be a power of 2. In other words, every prime of the form 2n + 1 is a Fermat number, and such primes are called Fermat primes. The only known Fermat primes are F0,...,F4.

Table of contents
1 Basic Properties
2 Primality of Fermat numbers
3 Factorisation of Fermat numbers
4 Relationship to Constructible Polygons

Basic Properties

The Fermat numbers satisfy the following recurrence relations

for n ≥ 2. From the last equation, it follows that no two Fermat numbers share a common factor. To see this, suppose that 0 ≤ i < j and Fi and Fj have a common factor a > 1. Then a divides both

and Fj; hence a divides their difference 2. Since a > 1, this means a = 2. This is a contradiction, because each Fermat number is clearly odd. As a corollary, we obtain another proof of the infinitude of the prime numbers: for each Fn, choose a prime factor pn; then the sequence {pn} is an infinite sequence of distinct primes.

Here are some other basic properties of the Fermat numbers:

(See floor function)

Primality of Fermat numbers

Fermat numbers and Fermat primes were first studied by Pierre de Fermat, who conjectured that all Fermat numbers are prime. Indeed, the first five Fermat numbers F0,...,F4 are easily shown to be prime. However, this conjecture was put to rest by Leonhard Euler in 1732 when he showed that

It is interesting to note how Euler found this factorisation. Euler had proved that every factor of Fn must have the form k2n+1 + 1. (In fact, the exponent n + 1 can be replaced by n + 2; this is Lucas's theorem.) For n = 5, this means that the only possible factors are of the form 64k + 1. It did not take Euler very long to find the factor 641 = 64*10 + 1.

It is widely believed that Fermat was aware of Euler's result, so it seems curious why he failed to follow through on the straightforward calculation to find the factor. One common explanation is that Fermat made a computational mistake and was so convinced of the correctness of his claim that he failed to double-check his work.

There are no other known Fermat primes Fn with n > 4. It is not known whether these are the only Fermat primes, and it is not even known whether or not there are infinitely many Fermat primes.

Factorisation of Fermat numbers

The main result which is helpful in determining the primality of Fermat numbers is the following test, due to Pepin:

Pepin's test -- Let Fn be a Fermat number. Then Fn is prime if and only if

Relationship to Constructible Polygons

Since at least the time of Euclid, it was known that many regular polygons were capable of being constructed by ruler and compass. The problem then arose, "For which positive integers n is the regular n-gon constructible with ruler and compass?". Carl Friedrich Gauss was the first to make progress on this problem by showing its relationship to Fermat primes. In 1796 (at the age of 19), Gauss showed that a sufficient condition for the regular n-gon to be constructible is that n is a power of 2 or the product of a power of 2 and distinct Fermat primes. In other words, if n is of the form n = 2kp1p2...ps, where k is a nonnegative integer and the pi are distinct Fermat primes, then the regular n-gon is constructible. The necessity of this condition was not proved until 1836 by Pierre Wantzel. A positive integer n is of the above form if and only if φ(n) is a power of 2, where φ(n) is Euler's totient function.

See also:

External links: References: