Fermat numbers

Two previous posts (here and here) present an alternative proof that there are infinitely many prime numbers using the Fermat numbers. Specifically, the proof is accomplished by pointing out that the prime factors of the Fermat numbers form an infinite set. This post takes a look at Fermat numbers in more details.

A Fermat number is of the form \displaystyle F_n=2^{2^n}+1 where n=0,1,2,3,\cdots. The numbers grow very rapidly since each Fermat number is obtained by raising 2 to a power of 2. The first several terms are 3, 5, 17, 257, 65,537, 4,294,967,297. They are named after the French mathematicians Pierre de Fermat (1601-1665). He demonstrated that the first 5 Fermat numbers F_0, F_1, F_2, F_3, F_4 are prime and conjectured that all Fermat numbers are prime. In 1732, Euler provided a counterexample to the conjecture by showing that

    \displaystyle F_5=2^{2^5}+1=2^{32}+1=4294967297=641 \times 6700417

Any Fermat number that is also a prime number is said to be a Fermat prime. Other than F_0, F_1, F_2, F_3, F_4, no additional Fermat primes have been discovered.

Euler likely did not factor F_5 by trial division. Euler discovered that the prime factors of Fermat numbers have a specific form. This discovery led to 641 being a factor of F_5. We discussed this result and other basic facts of Fermat numbers as well as the Pepin’s test, which is a primality testing algorithm that works on Fermat numbers as well as the Pepin’s test.


Basic Results

One interesting fact is that Fermat numbers can be defined (or generated) recursively. Any Fermat number can be derived by taking the product of all the preceding Fermat numbers plus 2. Another basic fact is that the Fermat numbers are pairwise relatively prime, i.e. any two Fermat numbers have no common factor other 1. These two facts are stated in Theorem 1 and Theorem 2 below, which are proved in this previous post.

Theorem 1
For n \ge 1, we have the following results:

  • F_n=(F_{n-1}-1)^2+1.
  • F_n=F_0 \times \cdots \times F_{n-1}+2.

Theorem 2
For i \ne j, F_i and F_j are relatively prime.

A corollary of Theorem 1 and Theorem 2 is that there are infinitely many prime numbers. Another corollary of Theorem 1 is that all Fermat numbers, except for the first two, end in the digit of 7.

Corollary 3
There are infinitely many prime numbers.

Corollary 4
For n \ge 2, the last digit of F_n is 7.

To see Corollary 3, if F_n is prime, then let p_n=F_n. If not, let p_n be the smallest prime factor of F_n. By Theorem 2, the prime numbers p_n are pairwise relatively prime, hence pairwise distinct.

To see Corollary 4, note that F_n \equiv 2 \ (\text{mod} \ F_j) for j <n (this follows from Theorem 1). In particular, F_n \equiv 2 \ (\text{mod} \ 5). Equivalently, F_n-2=5k for some integer k. Since all F_n are odd, k is odd. Thus k=2j+1 for some j and F_n-2=10j+5. Subtracting 5 on both sides gives F_n-7=10j. This means that F_n \equiv 7 \ (\text{mod} \ 10).


The Prime Factors of Fermat Numbers

The Fermat numbers F_0 to F_{4} are prime. No additional Fermat primes had been identified since the time of Fermat. The Fermat numbers F_5 to F_{11} have been completely factored. With a few exceptions, the numbers F_{12} to F_{43} are partially factored. The exceptions: F_{20} and F_{24} are shown to be composite (with no known factors) while F_{33} to F_{35} and F_{40} and F_{41} have unknown status. Beyond F_{43}, there is a long list of partially factored F_n for 43<n \le 3329780. For the most up to date factoring status of Fermat numbers, see here.

There are no known Fermat primes other than the first five (F_0 to F_4). For the Fermat numbers beyond F_4, there are only finite number of them that are known to be composite. There are interesting and natural questions that can be raised about Fermat numbers. Is there another Fermat prime? Are there infinitely many Fermat primes (Eisenstein 1844)? Are there infinitely many composite Fermat numbers? Is F_n composite for all n>4?

In this section, we consider some basic facts about prime factors of Fermat numbers. What if we relax the definition of Fermat numbers by considering the numbers 2^m+1 where m is a nonnegative integer that does not necessarily have to be a power of 2? Can 2^m+1 be a prime number? It turns out that if we want to look at 2^m+1 that are prime numbers, we have to restrict our attention to Fermat numbers. This is stated more formally in Theorem 5.

Theorem 5
If 2^m+1 is a prime number, then m is a power of 2.

Proof of Theorem 5
Let 2^m+1 be a prime number. Let m=b \times 2^w where w \ge 0 and b \ge 1 is odd. Now 2^m+1=(2^{2^w})^b+1. To make it easy to see the argument, let A=2^{2^w} and B=-1. Note that (2^{2^w})^b+1=A^b-B^b. Furthermore A-B=2^{2^w}+1 divides A^b-B^b. This means that 2^{2^w}+1 is a factor of 2^m+1. Since 2^m+1 is prime, 2^{2^w}+1=2^m+1. That implies that b=1. As a result, m=2^w. \square

Theorem 5 is a useful result. It tells us that 2 raised to odd power plus 1 can never be prime. For example, 2^{11}+1 is not prime. Without any calculation, we known that 2^w+1 is composite if w = 2,305,843,009,213,693,953. On the other hand, 2 raised to any even power is not prime as long as the even power is not a power of 2. For example, 2^{20}+1 is not prime. Just to be clear, when m is a power of 2, it does not mean 2^m+1 is a prime. The Fermat number F_5 is a counterexample. The property in Theorem 5 is a necessary and not a sufficient condition. So far we only know of five example of prime 2^m+1 where m is a power of 2. We next consider the prime factors of a Fermat number.

Theorem 6 (Euler-Lucas)
For any integer n \ge 2, any prime factor p of F_n=2^{2^n}+1 is of the form p=k \times 2^{n+2}+1 for some integer k.

Proof of Theorem 6
Let p be a prime factor of F_n. From the definition of Fermat numbers, observe that 2^{2^n} \equiv -1 \ (\text{mod} \ p). Squaring both sides gives 2^{2^{n+1}} \equiv 1 \ (\text{mod} \ p). We claim that the order of the element 2 modulo p is 2^{n+1}. Suppose the order of the element 2 modulo p is 2^{j} where j<n+1, equivalently j \le n. Then 2^{2^{j}} \equiv 1 \ (\text{mod} \ p) and 2^{2^{n}} \equiv 1 \ (\text{mod} \ p), a contradiction. Thus the claim is true.

Furthermore, the order of 2 modulo p would divide \phi(p)=p-1 where \phi(\cdot) is the Euler's phi function (see corollary 5 here). Thus 2^{n+1} would divide p-1 or p=j \times 2^{n+1}+1 for some j.

The result in the preceding paragraph is the result of Euler. Now to the improvement by Lucas. Since n \ge 2, p \equiv 1 \ (\text{mod} \ 8). By the second supplement to the law of quadratic reciprocity (Theorem 8 found here), the element 2 is a quadratic residue modulo p. This means that r^2 \equiv 2 \ (\text{mod} \ p) for some integer r. Raise both sides to 2^{n+1} gives r^{2^{n+2}} \equiv 2^{2^{n+1}} \equiv 1 \ (\text{mod} \ p). We claim that the order of the element r modulo p is 2^{n+2}. Suppose the order of the element r modulo p is 2^{j} where j<n+2, or equivalently j \le n+1. Then r^{2^{j}} \equiv 1 \ (\text{mod} \ p) and r^{2^{n+1}} \equiv 1 \ (\text{mod} \ p). Note that r^{2^{n+1}} \equiv (r^2)^{2^n} \equiv 2^{2^n} \equiv 1 \ (\text{mod} \ p). This contradicts the congruence 2^{2^n} \equiv -1 \ (\text{mod} \ p) observed earlier. The claim is established.

As a result of the fact that the order of the element r modulo p is 2^{n+2}, 2^{n+2} divides \phi(p)=p-1. Equivalently, p=k \times 2^{n+2}+1 for some k. \square

When a Fermat number is determined to be composite (e.g. via Theorem 7 below), Theorem 6 indicates that its prime factors are of a certain form. For the Fermat number F_5, the factor 641 can be derived as follows. First, note the following two relations.

    641=5 \times 2^7+1


From the first fact, 5 \cdot 2^7 \equiv -1 \ (\text{mod} \ 641). Raising both sides to 4 gives 5^4 \cdot 2^{28} \equiv 1 \ (\text{mod} \ 641). From the second fact, 5^4 \equiv -2^4 \ (\text{mod} \ 641). Combining the two congruences gives -2^4 \cdot 2^{28} \equiv - 2^{32} \equiv 1 \ (\text{mod} \ 641), which means that 641 divides F_5=2^{32}+1.


Primality Testing of Fermat Numbers

Because the Fermat numbers grow so rapidly, factoring large Fermat numbers is a challenge. However, there is a polynomial-time algorithm that determines the primality of a Fermat number (see Theorem 7 below). But even this test is limited because of the rapid growth of Fermat numbers.

Theorem 7 (Pepin’s Test)
For n \ge 1, the Fermat number F_n=2^{2^n}+1 is a prime number if and only if \displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n).

Proof of Theorem 7
Suppose that F_n=2^{2^n}+1 is prime where n \ge 1. We claim that the number 3 is a quadratic nonresidue modulo F_n. Once this is established, the congruence \displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n) would follow by appealing to Euler’s criterion (see Theorem 1 here). To see the claim, note that

    \displaystyle \biggl( \frac{3}{F_n} \biggr)=\biggl( \frac{F_n}{3} \biggr)=\biggl( \frac{2}{3} \biggr)=-1

The above symbols are Legendre symbols since F_n is a prime number. The first symbol can be flipped without changing the sign since F_n \equiv 1 \ (\text{mod} \ 4). This is according to the law of quadratic reciprocity (see Theorem 6 here). It follows from the first bullet point in Theorem 1 that F_n \equiv 2 \ (\text{mod} \ 3) for all n \ge 1. Thus the second Legendre symbol above is the same as the third symbol. Lastly, 2 is a quadratic nonresidue modulo 3. Thus the third Legendre symbol above equals -1. By Euler’s criterion, this means that the congruence \displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n) holds.

The other direction uses Lucas’ primality test, which is a test that proves the primality for any integer p such that the factorization of p-1 is completely known. Fermat numbers fit the requirement since F_n-1 is a power of 2. For the statement and proof of Lucas’ primality test, see Theorem 1 here. To show the other direction, suppose that \displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n) where n \ge 1. Clearly, \displaystyle 3^{F_n-1} \equiv 1 \ (\text{mod} \ F_n). By Lucas’ primality test, F_n is prime. \square

The number 3 is the base used in the Pepin’s test as stated in Theorem 7. Other bases can be used, e.g. 5. The following is the Pepin’s test using 5 as the base.

Theorem 8 (Pepin’s Test)
For n \ge 2, the Fermat number F_n=2^{2^n}+1 is a prime number if and only if \displaystyle 5^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n).

The proof for Theorem 8 works similarly. If F_n is prime, it can be shown that 5 is a quadratic nonresidue modulo F_n.

To determine whether a given Fermat number F_n is prime, simply compute the congruence \displaystyle 3^{\frac{F_n-1}{2}} \ (\text{mod} \ F_n). If the result is -1, then F_n being tested is a prime number. If the congruence is not -1, then F_n is composite. Note that the results from Pepin’s test can only tell whether the given Fermat number is prime or composite. If the test result says composite, it does not indicate what the factors are. The following shows the test results for F_4 to F_{10}.

    \displaystyle 3^{\frac{F_4-1}{2}} \equiv 65536 \equiv -1 \ (\text{mod} \ F_4)

    \displaystyle 3^{\frac{F_5-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_5)
    where T = 10,324,303
    and F_5 = 4,294,967,297

    \displaystyle 3^{\frac{F_6-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_6)
    where T = 11,860,219,800,640,380,469
    and F_6 = 18,446,744,073,709,551,617

    \displaystyle 3^{\frac{F_7-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_7)
    where T = 110,780,954,395,540,516,579,111,562,860,048,860,420
    and F_7 = 340,282,366,920,938,463,463,374,607,431,768,211,457

    \displaystyle 3^{\frac{F_8-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_8)
    where T = 005,864,545,399,742,183,862,578,018,016,183,410,025,465,491,904,722,516,203,269,973,267,547,486,512,819
    and F_8 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,937

    \displaystyle 3^{\frac{F_9-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_9)
    where T =
    and F_9 =

    \displaystyle 3^{\frac{F_{10}-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_{10})
    where T =
    and F_9 =



The above calculations can be performed on a calculator that can handle modular exponentiation or be programmed in a computer. The above calculations point to the reality that it is much easier to determine the status of primality/compositeness of a number than the factorization. For example, the compositeness of F_8 was known in 1909 but the factors were not found until 1980.

The modular exponentiations displayed above, 3 raised to (F_n-1)/2, can be accomplished by performing a series of squaring and multiplications. This approach is called the square-and-multiply approach or the fast powering algorithm. In this algorithm, the binary expansion of the exponent is used to convert the exponentiation into a series of squarings and multiplications. See here for a description of the fast powering algorithm. See here for a simpler description. One interesting point that can be made about the calculation for the Pepin’s test is that the exponent is a power of 2. As a result, there is only one non-zero bit in the binary expansion (the highest bit). So the square-and-multiply only consists of squarings. In any programming attempt, the “multiply” part can be skipped.

The algorithm described in Theorem 7 (Pepin’s test) is a polynomial-time algorithm assuming that the input F_n is written in binary or decimal numbers. It seems that one can simply apply Pepin’s test on larger and larger Fermat numbers to gain more insight on the open questions on Fermat numbers. However, Pepin’s test, though efficient, is also a limited test. Because the exponent in the test is a power of 2 that increases rapidly, the test reaches a computational limit rather quickly.

Let’s look at the computational limit through F_{33}, which is the least Fermat number with unknown status. It has 2,585,827,973 decimal digits. In applying Pepin’s test, the exponent would be 2^{2^{33}-1}, which has 2^{33} = 8,589,934,593 many bits in the binary expansion (that’s the number of squarings required in the fast powering algorithm, over 8.5 billions)! Thus applying Pepin’s test (in conjunction with the fast powering algorithm) on the larger Fermat numbers is no small feat. The following comments from [1] give a good perspective on the Pepin’s test.

    The first Fermat number of unresolved character is thus F_{33}. By conventional machinery and Pepin test, the resolution of F_{33} would take us well beyond the next ice age! So the need for new algorithms is as strong as can be for future work on giant Fermat numbers.

According to the comments made in Wikipedia, Pepin’s test had been used 8 times in resolving the prime/composite status of Fermat numbers. To tackle large Fermat numbers, technology improvement (hardware, software and algorithm) will be needed. Thus progress may take decades or more.

There is one interesting question about Pepin’s test. What are all the possible bases that can be used in this test? Are there other bases beside 3 and 5? This is discussed in in another blog post.



  1. Crandall R., Pomerance C,Prime Numbers, A Computational Perspective, Second Edition, Springer, New York, 2005

\copyright \ 2016 \text{ by Dan Ma}

Tweaking a proof of the infinitude of primes

This blog presents two proofs of the infinitude of primes. The first one is the standard proof that is due to Euclid (around 300 BC). The second one is due to Christian Goldbach (from a letter to Leonhard Euler in 1730). This post attempts to generalize the second one. The goal is to capture the essence of the proof and in the process gains a better perspective. Reading the second proof is not a prerequisite. The reader is welcome to compare the argument here with the previous proof to appreciate the economy that is in the tweaked proof.


The Tweak

The existence of the following sequence will imply that there are infinitely many prime numbers.

    There is a sequence of positive odd integers x_0,x_1,x_3, \cdots such that

    • x_0 < x_1 < x_3 < \cdots,
    • any two elements of the sequence are relatively prime, i.e. for i \ne j, the terms x_i and x_j have no common divisor other than 1.

If such a sequence exists, we can infer an infinite sequence of prime numbers. Note that each term x_j is a product of distinct primes. Let p_j be the smallest prime factor of x_j. The prime numbers p_j must be distinct since the elements in the sequence x_0,x_1,x_3, \cdots are pairwise relatively prime.

How do we know if such a sequence exists? It can be defined recursively. Let x_0<x_1 be any odd positive integers that are relatively prime. For example, x_0=3 and x_1=5. Another example: x_0=21 and x_1=55. Then for each n>1, let x_n=x_0 \times x_1 \times \cdots \times x_{n-1}+2. Clearly the sequence is increasing. To see that any two terms of the sequence are relatively prime, let j<n and let d be a common divisor of x_j and x_n. Since d divides x_j, it is clear that d divides x_0 \times x_1 \times \cdots \times x_{n-1}. This means that d divides x_n-x_0 \times x_1 \times \cdots \times x_{n-1}=2. With d being odd and d dividing 2, it must be that d=1.

The proof in the previous post essentially uses the above argument with the first two terms fixed at x_0=3 and x_1=5. With these two initial choices, it can be shown that the sequence x_0,x_1,x_3, \cdots consists of the Fermat numbers. It is nice to know that the resulting sequence consists of the Fermat numbers. However, for proving that primes are infinite, the fact about Fermat numbers is immaterial. For example, if the initial two terms are x_0=21 and x_1=55, the same argument will still lead to an infinite sequence of prime numbers. Using Fermat numbers is one way to derive the sequence in question. Sometimes a broader picture picture can be obscured by being too specific in the argument.


An Equivalent Statement

The above argument for the infinitude of primes points to the fact that the existence of an infinite sequence of prime numbers is reduced to the existence of a sequence as described in the above argument. We have the following theorem.

The following two statements are equivalent.

  • There exists a sequence of positive odd integers x_0,x_1,x_3, \cdots such that x_0 < x_1 < x_3 < \cdots and such that any two terms of the sequence are relatively prime.
  • There are infinitely many prime numbers.

It is clear that if there are infinitely many primes, the sequence x_0,x_1,x_3, \cdots can simply be made the primes. So one direction is obvious. The other direction is proved by the above argument.

The theorem essentially says that the “infinity” of primes is identical to the “infinity” of numbers that are pairwise relatively prime. Of course, the purpose of discussing the latter is to give an argument that there are infinitely many primes.

\copyright \ 2016 \text{ by Dan Ma}