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 where . 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 , , , , are prime and conjectured that all Fermat numbers are prime. In 1732, Euler provided a counterexample to the conjecture by showing that
Any Fermat number that is also a prime number is said to be a Fermat prime. Other than , , , , , no additional Fermat primes have been discovered.
Euler likely did not factor 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 . 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.
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.
For , we have the following results:
For , and 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.
There are infinitely many prime numbers.
For , the last digit of is 7.
To see Corollary 3, if is prime, then let . If not, let be the smallest prime factor of . By Theorem 2, the prime numbers are pairwise relatively prime, hence pairwise distinct.
To see Corollary 4, note that for (this follows from Theorem 1). In particular, . Equivalently, for some integer . Since all are odd, is odd. Thus for some and . Subtracting 5 on both sides gives . This means that .
The Prime Factors of Fermat Numbers
The Fermat numbers to are prime. No additional Fermat primes had been identified since the time of Fermat. The Fermat numbers to have been completely factored. With a few exceptions, the numbers to are partially factored. The exceptions: and are shown to be composite (with no known factors) while to and and have unknown status. Beyond , there is a long list of partially factored for . For the most up to date factoring status of Fermat numbers, see here.
There are no known Fermat primes other than the first five ( to ). For the Fermat numbers beyond , 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 composite for all ?
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 where is a nonnegative integer that does not necessarily have to be a power of 2? Can be a prime number? It turns out that if we want to look at that are prime numbers, we have to restrict our attention to Fermat numbers. This is stated more formally in Theorem 5.
If is a prime number, then is a power of 2.
Proof of Theorem 5
Let be a prime number. Let where and is odd. Now . To make it easy to see the argument, let and . Note that . Furthermore divides . This means that is a factor of . Since is prime, . That implies that . As a result, .
Theorem 5 is a useful result. It tells us that 2 raised to odd power plus 1 can never be prime. For example, is not prime. Without any calculation, we known that is composite if = 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, is not prime. Just to be clear, when is a power of 2, it does not mean is a prime. The Fermat number 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 where is a power of 2. We next consider the prime factors of a Fermat number.
Theorem 6 (Euler-Lucas)
For any integer , any prime factor of is of the form for some integer .
Proof of Theorem 6
Let be a prime factor of . From the definition of Fermat numbers, observe that . Squaring both sides gives . We claim that the order of the element 2 modulo is . Suppose the order of the element 2 modulo is where , equivalently . Then and , a contradiction. Thus the claim is true.
Furthermore, the order of 2 modulo would divide where is the Euler's phi function (see corollary 5 here). Thus would divide or for some .
The result in the preceding paragraph is the result of Euler. Now to the improvement by Lucas. Since , . By the second supplement to the law of quadratic reciprocity (Theorem 8 found here), the element 2 is a quadratic residue modulo . This means that for some integer . Raise both sides to gives . We claim that the order of the element modulo is . Suppose the order of the element modulo is where , or equivalently . Then and . Note that . This contradicts the congruence observed earlier. The claim is established.
As a result of the fact that the order of the element modulo is , divides . Equivalently, for some .
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 , the factor 641 can be derived as follows. First, note the following two relations.
From the first fact, . Raising both sides to 4 gives . From the second fact, . Combining the two congruences gives , which means that 641 divides .
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 , the Fermat number is a prime number if and only if .
Proof of Theorem 7
Suppose that is prime where . We claim that the number 3 is a quadratic nonresidue modulo . Once this is established, the congruence would follow by appealing to Euler’s criterion (see Theorem 1 here). To see the claim, note that
The above symbols are Legendre symbols since is a prime number. The first symbol can be flipped without changing the sign since . This is according to the law of quadratic reciprocity (see Theorem 6 here). It follows from the first bullet point in Theorem 1 that for all . 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 holds.
The other direction uses Lucas’ primality test, which is a test that proves the primality for any integer such that the factorization of is completely known. Fermat numbers fit the requirement since 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 where . Clearly, . By Lucas’ primality test, is prime.
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 , the Fermat number is a prime number if and only if .
The proof for Theorem 8 works similarly. If is prime, it can be shown that 5 is a quadratic nonresidue modulo .
To determine whether a given Fermat number is prime, simply compute the congruence . If the result is -1, then being tested is a prime number. If the congruence is not -1, then 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 to .
where = 10,324,303
and = 4,294,967,297
where = 11,860,219,800,640,380,469
and = 18,446,744,073,709,551,617
where = 110,780,954,395,540,516,579,111,562,860,048,860,420
and = 340,282,366,920,938,463,463,374,607,431,768,211,457
where = 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 = 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
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 was known in 1909 but the factors were not found until 1980.
The modular exponentiations displayed above, 3 raised to , 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 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 , 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 , which has = 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  give a good perspective on the Pepin’s test.
The first Fermat number of unresolved character is thus . By conventional machinery and Pepin test, the resolution of 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.
- Crandall R., Pomerance C,Prime Numbers, A Computational Perspective, Second Edition, Springer, New York, 2005