Fermat Numbers: A False Conjecture Leads to Fun and Fascination

Fermat Numbers: A False Conjecture Leads to Fun and Fascination 1 Introduction The French mathematician Pierre de Fermat (1601–1665) was a veritable giant of number theory whose discoveries, and especially, whose conjectures and unproven assertions, kept mathematicians hard at work for several centuries that followed. Indeed, the first two issues of this magazine both featured his work: the first issue reviewed a book ([1]) on the history of what is known as “Fermat’s Last Theorem,” while the second issue, in an article on the four squares theorem ([2]), describes Fermat’s work on primes that are representable as sums of two squares. Besides these two well known contributions, Fermat is known for a whole host of other theorems in mathematics. He was a lawyer by training, but his passion was mathematics. He shone in arithmetic (which in its more advanced form, is what we call number theory today), but made seminal contributions in other parts of mathematics as well, and even in physics. Great mathematicians, and Fermat was squarely in that league, are characterized by deep intuition that enables them to see mathematical truths that others are not yet able to see. But great mathematicians are also human, and occasionally, they are wrong. Fermat himself was wrong on at least one n mathematical matter: the issue of whether numbers of the form 22 + 1 are prime. These numbers are the subject of this article. Recall first the convention when interpreting numbers written with ren n peated exponents: 22 + 1 is to be interpreted as 2(2 ) + 1 (and not (22)n + 1). n 0 Let us write Fn for the number 22 + 1, so that F0 = 22 + 1 = 21 + 1 = 3, F1 = 5, F2 = 17, etc. Fermat claimed that the numbers Fn are prime for all 1 integers n = 1, 2, . . . . In fact, he first claimed to have a proof, but later discovered an error in it ([3, Foreward]). However, he appeared to still believe in the truth of his claim. It is thus fair to rename his claim as a conjecture. Indeed, F0 , F1 , and F2 above are clearly prime. So is F3 = 28 + 1 = 257 and F4 = 216 + 1 = 65537. But there the list is broken! Euler, who lived approximately a century after Fermat (1707–1783) showed that F5 , which is a ten-digit integer, is not prime: it is divisible by 641. Thus, Fermat’s n conjecture on the numbers 22 + 1 was false! But there is another characterization of great mathematicians that is relevant here—the very objects they think about turn out to be fascinating and deep, even if these mathematicians occasionally make false assertions n about them! Such is indeed the case with numbers of the form 22 + 1, now n appropriately called Fermat Numbers. (Numbers of the form 22 + 1 that are prime are now referred to as Fermat primes.) Fermat numbers have proven to have many charming properties, and have turned out to have intriguing connections to other parts of mathematics, as well as to computer science. 2 Identities and the Infinitude of Primes Let us start with some very pretty identities that these Fermat numbers satisfy, the proofs of all of which are fun exercises for high school students: they involve nothing more than simple algebra and induction. 1. Fn = (Fn−1 − 1)2 + 1, for n ≥ 1. 2. Fn = F0 · F1 · F2 · · · Fn−1 + 2, for n ≥ 1. n−1 3. Fn = 22 F0 · F1 · F2 · · · Fn−2 + Fn−1 , for n ≥ 2. 2 4. Fn = Fn−1 − 2(Fn−2 − 1)2 , for n ≥ 2. n We will prove the first two here: For the first identity, note that 22 = n−1+1 n−1 n−1 22 = 22 ·2 = (22 )2 = (Fn−1 − 1)2 . Adding one everywhere, we n find Fn = 22 + 1 = (Fn−1 − 1)2 + 1, as desired. As for the second, we use induction. When n = 1, the assertion reads F1 = F0 + 2, which is clearly true since F1 = 5 and F0 = 3. Now assume that the statement has been proved true for some specific n ≥ 1. Consider F0 · F1 · F2 · · · Fn−1 · Fn + 2. The induction hypothesis shows, upon grouping all but the last factor in the first summand, that this expression equals (Fn − 2)Fn + 2, which is Fn2 − 2Fn + 2, 2 or what is the same thing, (Fn − 1)2 + 1. But by the first identity that which we just proved, (Fn − 1)2 + 1 = Fn+1 ! By induction, the second identity must be true for all integers n ≥ 1. There is an immediate consequence of the second identity above: the last digit of every Fermat number (for n ≥ 2) must be 7! This is because for any n ≥ 2, we find Fn = 3 · 5 · F2 · · · Fn−1 + 2 = 5(3 · F2 · · · Fn−1 ) + 2. Hence, Fn leaves a remainder of 2 upon dividing by 5. Thus, the last digit of Fn must n either be 2 or 7. But by definition, Fn = 22 + 1 is odd. It follows that for n ≥ 2, every Fn must indeed end in 7. This is pretty! The second consequence is that the Fermat numbers are pairwise relatively prime, that is, for any distinct nonnegative integers i and j, gcd(Fi , Fj ) = 1. This is attributed to Goldbach (who is well known for a conjecture that is as yet unproven: Every even integer greater than 2 is expressible as a sum of two primes). For, suppose that j > i, and suppose that gcd(Fi , Fj ) > 1. Thus, some prime p divides both Fi and Fj . But since Fj = F0 · · · Fi · · · Fj−1 + 2, and since p divides both the left side and the first term on the right, we find that p divides 2. Thus, p must be 2. But this means that Fi and Fj are even, which contradicts the fact that the Fermat numbers are odd! The fact that the Fermat numbers are relatively prime immediately leads to a new proof of the infinitude of primes: Since the primes that divide any Fi must be disjoint from those that divide Fj for i 6= j, and since there are infinitely many Fermat numbers, it follows at once that there must be infinitely many primes! 3 Fermat Numbers and Constructibility of Polygons Recall the problems of constructibility handed to us by the Greeks: using only straightedge and compass, construct line segments of certain lengths, and angles of certain measures. It was an open problem for a very long time, for instance, whether one could trisect an arbitrary angle using straightedge or compass, as for that matter, whether one could “square the circle,” that is, find the length of the side of a square whose area is that of the circle of radius 1, and whether one could “double the cube,” that is, construct the length of the side of a cube whose volume is twice that of the cube with side 1. These 3 problems are easy to solve once one has at one’s command techniques from Field Theory (known in an earlier guise as the Theory of Equations); this theory was certainly unknown to the Greeks. Indeed, we know now that the answer all three questions is: No! A specific problem in this context was the constructibility of regular ngons, for various values of n. Thus, a regular 3-gon is an equilateral triangle, a regular 4-gon is a square, a regular 5-gon is a pentagon with equal sides, and so on. Whether a regular n-gon can be constructed using a straightedge and compass quickly reduces to the question of whether the angle 2π/n can be constructed. This problem was investigated by that Great Master, Carl Friedrich Guass. (Gauss ranks among the greatest mathematicians ever, when measured not just by his own productivity but by the new areas of mathematics he initiated; his results to this date are a source of joy and wonder. His influence on mathematics and indeed all sciences, ranks with that of Newton.) Gauss showed that the regular 17-gon is constructible (note that 17 is F2 !), and went on to show that any regular n-gon (n ≥ 3) can be constructed if the prime factorization of n is of the form 2k p1 · · · pl , where the t pi are distinct primes of the form 22 + 1—Fermat numbers again! This is an instance of how objects and questions about these objects considered by great mathematicians (in this case Fermat) can turn out to have deep significance in mathematics, not often apparent at first. Thus, the question of t whether, for a given t, the tth Fermat number 22 + 1 is prime turns out to be more than just a curiosity: it is vitally connected to whether an n-gon can be constructed. The reason why a regular n-gon with the described prime factorization of n is constructible, lies in Field Theory. For the case where n is a prime—call it p instead—this theory tells us that the regular p-gon is constructible if and only if p − 1 is a power of 2. Thus, a regular p-gon is constructible if and only if p = 2k + 1 for some integer k. Now one can see quite easily that 2k + 1 cannot be prime unless k is itself a power of 2. For, suppose k = 2l b for some l l odd integer b > 1. Then 2k + 1 = 22 b + 1 = (22 )b + 1. Now it is a high school fact (or else, it can be proven as a high school exercise) that xb + 1 is l divisible by x + 1 if b is odd. Thus, if b > 1, p = (22 )b + 1 would have the l strictly smaller divisor 22 + 1, contradicting the fact that p is prime. Hence, the condition from Field Theory becomes: a regular p-gon is constructible if and only if p is a Fermat prime! The condition for the constructibility of a regular n-gon for a general n 4 Figure 1: French stamp commemorating the 400th birth anniversary of Fermat; perhaps one day there will be another stamp depicting the next Fermat prime after F4 ! (Image courtesy [8] and [9].) follows from the condition just described for the case where n is prime, using standard reductions also furnished by Field Theory. Indeed, the condition for a general n-gon is also an if and only if statement: a regular n-gon is constructible if and only if n is of the form described by Gauss. Gauss proved the sufficiency of the condition, but his proof of the necessity had a gap that was filled later ([3, Chap. 16]). 4 Primality of the Fermat Numbers n Let us turn to the original conjecture of Fermat, that the numbers 22 + 1 are prime for all n = 0, 1, . . . . We know, thanks to Euler, that while F0 through F4 are prime, F5 is not. For what other values of n is Fn known to be prime? The answer, more than three hundred and fifty years after Fermat made his first conjecture, is: None! Now that does not mean that no Fn is prime for n ≥ 5. All it means is that no one has conclusively shown that any of the various Fn for n ≥ 6 is prime. In fact, what have been established, similar to the case of F5 , are results in the opposite direction: the numbers F6 through F32 have all shown to be composite ([4]). Besides these, Fn is known to be composite for many other sporadic values of n, such as n = 36, 71, 99, 517, 2059, 6390, 17748 to select just a sample ([4]). 5 What makes the determination of the primality of Fn so hard is that, thanks to the presence of the double exponent, the number of digits in Fn grows very rapidly as n becomes large. In fact, Exercise (2) in Section 5 ahead clearly shows that the growth in the number of digits is exponential. On the other hand, there is a very pretty result on the possible prime factors of Fn : Euler showed that any prime that divides Fn must be of the form k · 2n+1 + 1, for some positive integer k. (The proof of this itself involves another famous theorem of Fermat known as Fermat’s Little Theorem: for any prime p and any integer a, ap − a is divisible by p.) Euler’s result was further sharpened by Lucas, who showed that the k in Euler’s result must be even. Thus, pulling out one 2 from k and multiplying it with 2m+1 in Euler’s result, we have Lucas’ result that any prime divisor of Fn must be of the form l · 2n+2 + 1 for some positive integer l. This result is the basis of certain attempts at showing Fn is prime for various n: run √ through all possibly integers of the form l · 2n+2 + 1 that are less than Fn and check if they divide Fn . Although easy to state, the computational power required to perform these calculations, even allowing for various mathematical tricks that are used to speed up this process, is stupendous for large n, simply because the numbers Fn are so large. There are distributed searches that are currently taking place over the internet: various groups of people fascinated by Fermat primes collectively divide the work among themselves by looking for divisors in restricted ranges of l (see [5] for instance). Anybody with a computer and access to the internet can join these searches: we encourage the reader to do so too! 5 Further Readings and Exercises We have only touched on some aspects of Fermat numbers: there are many more very charming features of these numbers, and many more connections with other parts of mathematics and computer science that we have just not had the space to describe. A wonderful reference for Fermat numbers is [3] (note the pun in its title!). Although quite an advanced text for a high school student, it nevertheless conveys the fun and the fascination of these numbers, and students will profit even by simply thumbing through the book. We also recommend the Wikipedia article ([6]) for another overview of some features of these numbers, as well as the MacTutor ([7]) biography of Fermat. We end with some further exercises that can be tackled by high school 6 students. 7