17 Lectures on Fermat Numbers

Frontmatter

1. Introduction

Abstract

The French mathematician Pierre de Fermat (1601–1665) became well known not only due to Fermat’s last theorem (proved in [Wiles] and [Taylor, Wiles]) and Fermat’s little theorem (proved by Euler), but also due to the conjecture that all the numbers

(1.1)

are prime. The numbers F _m are called Fermat numbers after him.

Michal Křížek, Florian Luca, Lawrence Somer

2. Fundamentals of Number Theory

Abstract

Throughout this book we shall mainly work with integers unless we specify otherwise. By N we denote the set {1, 2, 3, ... } of all natural numbers, i.e., all positive integers. A natural number p is said to be prime if p > 1 and p is divisible only by p and 1. Thus, the natural numbers are divided into the unit 1, prime numbers, and composite numbers. Notice that we can find arbitrarily many successive natural numbers that are all composite. Indeed, for any n > 1 the sequence n! + 2, n! + 3, ... , n! + n contains n - 1 successive integers that are evidently composite. On the other hand we have the following theorem of Euclid:

Theorem 2.1(Euclid)

The number of primes is infinite.

 

Michal Křížek, Florian Luca, Lawrence Somer

3. Basic Properties of Fermat Numbers

Abstract

First we present a few recurrence formulae for the Fermat numbers. Most of these can be found in the paper [Grytczuk] (see also [Schram]).

Michal Křížek, Florian Luca, Lawrence Somer

4. The Most Beautiful Theorems on Fermat Numbers

Abstract

A power of two increased by one can divide another power of two increased by one, e.g., 2 + 1 | 8 + 1 or 4 + 1 | 64 + 1. However, Euler’s contemporary Christian Goldbach proved that the Fermat numbers are pairwise coprime.

Michal Křížek, Florian Luca, Lawrence Somer

5. Primality of Fermat Numbers

Abstract

Remark 5.1. Notice that the number is prime, but the numbers 2³ + 1 and are composite (cf. Appendix A). This example shows that if 2 ⁿ prime, then need not be prime and vice versa (see [Sierpiński, 1970, Problem 141]).

Michal Křížek, Florian Luca, Lawrence Somer

6. Divisibility of Fermat Numbers

Abstract

In 1878, Édouard A. Lucas established a criterion concerning the general form of prime divisors of the Fermat numbers, namely, that every prime divisor p of F _m, m > 1, satisfies the congruence (see, e.g., [Lucas, 1878b], [Dickson, p. 376])

.

Michal Křížek, Florian Luca, Lawrence Somer

7. Factors of Fermat Numbers

Abstract

The factors k2 ⁿ +1, k, n ∈ ℕ of Fermat numbers have been intensively studied by many authors, e.g., [Artjuhov], [Banlie], [Bosma], [Brent, 1982], [Brillhart, Lehmer, Selfridge], [Cormack, Williams], [Golomb, 1976], [Keller 1983, 1992], [Křížek, Chleboun, 1994, 1997], [Papademetrios], [Shorey, Stewart], [Williams, 1988]. In 1878, F. Proth stated the following theorem (see [Proth, 1878b, 1978c] and see [Robinson, 1957b], [Sierpiński, 1964a] for proofs of this theorem), which can be applied to verify easily the primality of divisors of Fermat numbers for k < 2 ⁿ (see [Robinson, 1957a] and [Robinson, 1958]; also compare with Suyama’s Theorem 4.22).

Michal Křížek, Florian Luca, Lawrence Somer

8. Connections of Fermat Numbers with Pascal’s Triangle

Abstract

Recall that Pascal’s triangle is the infinite triangle (C(n, j)) having the rows indexed by n = 0, 1, , the columns indexed by j = 0, 1, , n, and entries that are simply the binomial coefficients

$$ C\left( {n,\,j} \right) = \left( \begin{gathered} n \hfill \\ j \hfill \\ \end{gathered} \right)\quad for\,all\,0 \leqslant j \leqslant n $$

(8.1)

.

Michal Křížek, Florian Luca, Lawrence Somer

9. Miscellaneous Results

Abstract

In this section we collect a few miscellaneous facts about the Fermat numbers. We start with a simple proof of the following result, which has been known since 1850. This result generalizes Remark 6.11 and Remark 6.17, which stated that no Fermat number can be a perfect square or a perfect cube.

Michal Křížek, Florian Luca, Lawrence Somer

10. The Irrationality of the Sum of Some Reciprocals

Abstract

Let {n _k } _k≥1 be an increasing sequence of positive integers. In this chapter we investigate some conditions under which the sum of the series

$$ \sum\limits_{k \geqslant 1} {\frac{1}{{{n_k}}}} $$

(10.1)

is an irrational number, and then we apply these results to the case for which the sequence {n _k } _k>1 is the sequence of Fermat numbers.

Michal Křížek, Florian Luca, Lawrence Somer

11. Fermat Primes and a Diophantine Equation

Abstract

In this chapter we find all solutions of the Diophantine equation

$$ \emptyset \left( {\left| {{x^n} - {y^n}} \right|} \right) = {2^j} $$

(11.1)

where ø is the Euler totient function, x and y are integers, and n and j are positive integers such that n ≥ 2. This problem was first solved in [Luca, 2000c]

Michal Křížek, Florian Luca, Lawrence Somer

12. Fermat’s Little Theorem, Pseudoprimes, and Superpseudoprimes

Abstract

In this chapter we show how to apply Fermat numbers to generate infinitely many pseudoprimes and superpseudoprimes. To define pseudoprimes and superpseudoprimes, we will need to make use of Fermat’s little theorem which is a centerpiece of number theory. It gives a fundamental property of primes and is the basis of most tests for primality.

Michal Křížek, Florian Luca, Lawrence Somer

13. Generalizations of Fermat Numbers

Abstract

We will explore generalizations of Fermat numbers that share many of the same properties of the Fermat numbers; these properties were given in earlier chapters. We will also investigate other numbers such as the Cullen numbers, which bear some resemblance to the Fermat numbers.

Michal Křížek, Florian Luca, Lawrence Somer

14. Open Problems

Abstract

The important thing is not to stop questioning. Albert Einstein

Several conjectures concerning the Fermat numbers have been resolved. We already know that Fermat’s claim that all F _m are primes was disproved by L. Euler.

Michal Křížek, Florian Luca, Lawrence Somer

15. Fermat Number Transform and Other Applications

Abstract

Up to now we have presented several useful applications of the Fermat numbers in number theory, e.g., in proving that there exist infinitely many primes and pseudoprimes, and in establishing the existence of Sierpiński numbers (see Remark 4.2, Theorems 12.1 and 7.4). However, there are more practical applications of F _m, as we shall see in this chapter. In particular, we introduce the use of Fermat numbers in number-theoretic transforms; in binary arithmetic modulo F _m, which leads to fast multiplication of large numbers; in pseudorandom number generators; in hashing schemes; in the chiral Potts model; and in an analysis of the logistic equation by means of divisors of Fermat numbers.

Michal Křížek, Florian Luca, Lawrence Somer

16. The Proof of Gauss’s Theorem

Abstract

Recall Gauss’s Theorem 4.3: There exists a Euclidean construction (i.e., by ruler and compass) of the regular n-gon if and only if

$$ n = {2^i}{p_1}{p_2} \cdot \cdot \cdot {p_j} $$

, where n ≥ 3, i ≥ 0, j ≥ 0, and j ₁, p ₂ . . . p_j are distinct Fermat primes.

Michal Křížek, Florian Luca, Lawrence Somer

17. Euclidean Construction of the Regular Heptadecagon

Abstract

Gauss’s theorem from the previous chapter establishes a remarkable necessary and sufficient condition for a Euclidean construction of regulär polygons. Euclid (≈ 330 – ≈ 260 B.C.) already knew how to construct regulär polygons with n sides by ruler and compass for

$$ n = {2^i}{3^j}{3^k} $$

where n ≥ 3 and i ≥ 0 are integers and j, k ∈ {0,1}. However, he did not know whether it is possible to construct the regular heptagon or nonagon. C. F. Gauss (see Figure 17.1) gave the answer to this question 2000 years later. When he was only nineteen (cf. Figure 17.2), he wrote a short treatise about the division of a circle into 17 equal parts by geometric means (see Figure 17.3 and (17.3)). Here he essentially used the fact that 17 is a Fermat prime. This fundamental discovery is presented on the base of his statue in Brunswick (in German Braunschweig), where he was born (see Figure 17.4).

Michal Křížek, Florian Luca, Lawrence Somer

Backmatter