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

F₀ = 2¹ + 1 = 3

F₁ = 2² + 1 = 5

F₂ = 2⁴ + 1 = 17

F₃ = 2⁸ + 1 = 257

F₄ = 2¹⁶ + 1 = 65537

F₅ = 2³² + 1 = 4294967297

F₆ = 2⁶⁴ + 1 = 18446744073709551617

F₇ = 2¹²⁸ + 1 = 340282366920938463463374607431768211457

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

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 F_i and F_j have a common factor a > 1. Then a divides both

and F_j; 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 F_n, choose a prime factor p_n; then the sequence {p_n} is an infinite sequence of distinct primes.

Here are some other basic properties of the Fermat numbers:

• If n ≥ 1, then F_n ≡ −1 (mod 6). (See modular arithmetic)
• If n ≥ 2, then F_n ≡ 17, 37, 57, or 97 (mod 100).
• The number of digits D(n,b) of F_n expressed in the base b is

(See floor function)

• No Fermat number can be expressed as the sum of two primes.
• No Fermat prime can be expressed as the difference of two pth powers, where p is an odd prime.

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 F₀,...,F₄ 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 F_n must have the form k2ⁿ⁺¹ + 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 F_n 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 F_n be a Fermat number. Then F_n 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 = 2^kp₁p₂...p_s, where k is a nonnegative integer and the p_i 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:

• Mersenne prime
• Lucas's theorem
• Pepin's test
• Pseudoprime
• Constructible number

External links:

• Sequence of Fermat numbers
• Prime Glossary Page on Fermat Numbers
• Generalized Fermat Prime search
• History of Fermat Numbers
• Unification of Mersenne and Fermat Numbers

References:

• 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Michal Krizek, Florian Luca, Lawrence Somer, Springer, CMS Books 9, ISBN 0387953329