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

    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}

Advertisements

2 thoughts on “Fermat numbers

  1. Pingback: Pepin’s Primality Test | Mathematical Cryptography

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s