# 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 (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. 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, 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, 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$

$641=5^4+2^4$

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$ =
03,487,842,192,292,834,160,828,677,804,926,452,873,307,656,935,026,758,634,839,951,511,167,913,561,583
764,893,191,647,059,299,508,808,058,740,314,515,096,456,032,583,684,082,248,245,196,170,211,101,691,254
and $F_9$ =
13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073
546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,097

$\displaystyle 3^{\frac{F_{10}-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_{10})$
where $T$ =
387,619,810,475,491,122,179,739,047,140,959,275,426,443,598,784,645,243,238,994,975,074,552,393,367
151,669,166,056,942,068,042,567,969,383,237,719,504,044,259,561,712,002,215,552,049,762,078,784,904
229,994,959,756,192,565,270,005,114,398,071,628,663,530,167,797,163,602,701,669,757,405,752,156,537
276,004,764,083,329,886,967,333,347,443,567,401,688,754,399,623,980,380,190,579,140,626,590,345,932,472,472
and $F_9$ =
179,769,313,486,231,590,772,930,519,078,902,473,361,797,697,894,230,657,273,430,081,157,732,675,805
500,963,132,708,477,322,407,536,021,120,113,879,871,393,357,658,789,768,814,416,622,492,847,430,639
474,124,377,767,893,424,865,485,276,302,219,601,246,094,119,453,082,952,085,005,768,838,150,682,342
462,881,473,913,110,540,827,237,163,350,510,684,586,298,239,947,245,938,479,716,304,835,356,329,624,224,137,217

____________________________________________________________________________

Remarks

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.

____________________________________________________________________________

Reference

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 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 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.

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}$