Some historical notes on proving Fermat numbers and cofactors to be composite

Catherine Cowie, August 2023

[Additions to 10 December 2024]

Vir Clarissime,
Jam diu animadverti omnem numerum 2^{2^x+p} + 1, ubi x et p sint numeri integri, divisum per 2^{2^x} + 1 relinquere 2, propterea quod (2^{2^x} + 1) (2^{2^x} – 1) est = (2^{2^x+1} – 1), rursus (2^{2^x+1} – 1) (2^{2^x+1} + 1) = (2^{2^x+2} – 1) et sic porro, donec perveniatur ad 2^{2^x+p} – 1, qui numerus binario minor est quam 2^{2^x+p} + 1; ex eo quidem certe sequitur omnes numeros seriei Fermatianae esse inter se primos, ut dicis; at quantulum hoc est ad demonstrandum omnes illos numeros esse absolute primos? Illustrious Sir,
I noticed a long time ago that any number 2^{2^x+p} + 1, where x and p are integers, divided by 2^{2^x} + 1 leaves 2, because (2^{2^x} + 1) (2^{2^x} – 1) is = (2^{2^x+1} – 1), again (2^{2^x+1} – 1) (2^{2^x+1} + 1) = (2^{2^x+2} – 1) and so on, until we reach 2^{2^x+p} – 1, which is a binary number smaller than 2^{2^x+p} + 1; from this it certainly follows that all the numbers of the Fermatian series are prime to each other, as you say; but how much is this towards demonstrating that all those numbers are absolutely prime?
… Ob hoc ipsum exemplum a te allatum, magis quam antea dubito de veritate theorematis Fermatiani; fieri enim potest ut minimus divisor alicuius numeri 2^{2^x} + 1 sit centum, vel centies mille notarum, quem usque ad finem mundi nemo inveniat. … Because of this very example brought by you, I doubt more than before the truth of Fermat’s theorem; for it is possible for the smallest divisor of any number 2^{2^x} + 1 to be a hundred, or a hundred thousand digits, which no one will find until the end of the world.

Christian Goldbach to Leonhard Euler, N.S. 31 July 1730 [24]

1. Introduction

The Fermat numbers are the first of two significant gifts Pierre de Fermat gave to number theory in the year 1640, the second being Fermat’s so-called ‘little’ theorem that prime p divides a^p – a for any integer a, and which if a is not divisible by p, that is to say a and p are coprime, yields the more familiar modern form of the theorem, a^p–1 ≡ 1 (mod p). The Fermat numbers F_m are the sequence of numbers 2^x + 1 where x is a power of 2 = 2^m, which Fermat was almost persuaded to believe were prime for all non-negative integers m. In this belief he was ultimately found to be incorrect, as in the following century Euler found a counterexample by factoring the case of m = 5. Since Euler’s discovery until the time of writing in mid-2023, only 323 more Fermat numbers have been found to be composite, and none further are known to be prime; an infinitude of Fermat numbers are of unknown character, with m = 33 the smallest.

The investigation of the Fermat numbers is a vast subject, of which this article concentrates on one aspect, the historical process of proving Fermat numbers or their cofactors to be composite, other than by the self-evident discovery of a factor. We begin with a historical prologue providing context for Fermat’s interest in this sequence, examine the development of primality tests at the end of the nineteenth century, before jumping ahead to the twentieth century and considering how primality tests were used to show the compositeness of small Fermat numbers prior to the discovery of factors. Manual calculations eventually gave way to increasingly powerful, programmed computations, so we also consider the record of cofactors of incompletely factorised Fermat numbers likewise being tested for compositeness, and verify these results using a custom computer program written by Gary B. Gostin, cofact [69]. Readers who only wish to consider the results of compositeness tests are encouraged to skim over the following two sections to section 4.

2. In principio erat numerum …

Fermat came to the sequence of numbers that bear his name by way of investigating another more famous sequence, the perfect numbers, which were drawn to his attention in 1640 by members of the epistolary network of analystes, who were mainly French mathematicians who shared their ideas through letters. This group was loosely centered around père Marin Mersenne, who facilitated the making of contacts between members of the group. At the start of 1640 Mersenne received a letter from Bernard Frénicle de Bessy, desiring him to inquire of Fermat, inter alia, ‘if it was not too much trouble’ could Fermat produce a 20-digit perfect number, or if he could not, whether he could instead go better than 20 digits [23].

This was a provocative challenge: the even perfect numbers (numbers equal to the sum of their smaller factors, including 1) had been known from the time of Euclid [19] to have a particular form, 2^p–1(2^p–1) where 2^p–1 is prime, and it was not yet known whether this was a necessary condition. It has been suggested (e.g. by Rashed [50]) that some Islamic scholars may have been aware of a proof of this converse, that for every prime p such that 2^p–1 is also prime, there exists an even perfect number, however there is at least one disproof of such a converse being widely known. A treatise ca. 1240 by Ibn Fallûs (fl.1220–1252) cited ten perfect numbers up to 35,184,367,894,528 [10], but included three that are not perfect and which correspond to p = 9, 11, and 23; p = 9 is a composite, prime power. In Europe a couple of centuries later, abacisti (a term for masters of the abacus) had claimed perfect numbers corresponding to p = 13 and 17 by ca. 1460 in two anonymous manuscripts, the provenance of which might be associated with the circle of Benedetto di Firenze [59]. A century later in 1588, Pietro Cataldi claimed perfect numbers corresponding to p = 17, 19, 23, 29, 31, and 37, and like Ibn Fallûs, three of these values are suspect. Cataldi’s later treatise of 1603 shows that only the cases p = 13, 17, and 19 were actually proved perfect by trial division, while the values of 2^p–1 asserted for p = 23 and beyond are offered as potentially yielding perfect numbers, with neither proof nor disproof of primality [13]. So by specifying a minimum of 20 digits, Frénicle wanted to know if Fermat possessed knowledge of a perfect number beyond p = 31, which corresponds to the 19-digit perfect number 2,305,843,008,139,952,128.

Fermat temporised by writing a long letter to Mersenne answering most of Frénicle’s other inquiries, and the second letter to Mersenne following is unfortunately fragmentary: Fermat answered there is no prime exponent p that could give rise to a 20-digit perfect number. The part of Fermat’s letter which followed is inconveniently missing but its content is strongly suggested from a retraction in his third letter to Mersenne. Evidently Fermat had gone on to claim p = 37 yielded a perfect number (or that he had been unable to find a new factor), which implied 2³⁷ – 1 was prime. This he wished to recant, by way of providing three propositions which included the new insight that composite members of the progression 2^p – 1 with prime exponents p will have factors of the form 2kp + 1, knowledge of which had allowed him to find by trial division the factors 47 and 223 for the cases of p = 23 and 37, k = 1 and 3, respectively.

These letters occupied the first half of 1640. By the second half of the year, Fermat had begun to notice the relationships between the subtractive 2^x – 1 and additive 2^x + 1 progressions; the former only generated primes if x was prime (albeit with exceptions, such as p = 11, 23, or 37), while members of the latter were always composite unless x was a power of 2 (as shown below Fermat refers to this sequence of exponents as la progression double). Moreover, he knew every odd exponent of the additive sequence had a factor of 3, and for every prime exponent p, if 2^p + 1 could be factored further, then these factors would take the 2kp + 1 form. In light of what is to come later, it also seems highly plausible that at the very least Fermat came independently to the result of Goldbach’s theorem, the inductive argument of which was quoted above, and which may also be run backwards as well as forwards:

F_m – 2 = 2^{2^m} – 1 = (2^{2^m–1} – 1)·(2^{2^m–1} + 1) for any arbitrarily large m, since 2^m is divisible by 2;
= (2^{2^m–2} – 1)·(2^{2^m–2} + 1) · F_m–1, since 2^m–1 is still divisible by 2;

= … = (2^2¹ – 1)·(2^2¹ + 1) · F₂ · … · F_m–1; note, M₂ = 2²–1 = 3 = 2^2⁰+1 = F₀

∴ F_m = F₀ · F₁ · F₂ · … · F_m–1 + 2

If he knew this result, Fermat would have seen that the theorem proves each member of the double exponent sequence to be coprime to every other member, since all members of the sequence are odd, and each exceeds the product of all previous terms by 2, ruling out divisibility. Further, if all members of the sequence could be shown to be prime, then they would provide another proof of the infinitude of prime numbers as well as a sure method for generating arbitrarily large primes. This was a discovery Fermat conjectured to be true, however he was careful to admit he lacked a proof. Thus in the second half of 1640 we find Fermat writing at least three letters to Frénicle directly, and at least once more to Mersenne. Of these, the first and most of the second letters to Frénicle are missing, but the fragment of the second included a discussion of what we now know as the Fermat numbers, which Fermat had evaluated up to F₆, as seen in this excerpt:

3. Mais voici ce que j’admire le plus : c’est que je suis quasi persuadé que tous les nombres progressifs augmentés de l’unité, desquels les exposants sont des nombres de la progression double, sont nombres premiers, comme 3. But here is what I admire most : it is that I am almost persuaded that all progressive numbers increased by one, whose exponents are numbers of the double progression, are prime numbers, such as
3 5 17 257 65537 4 294 967 297 3 5 17 257 65537 4 294 967 297

et le suivant de 20 lettres and the next of 20 digits

18 446 744 073 709 551 617; etc. 18 446 744 073 709 551 617; etc.

Je n’en ai pas la démonstration exacte, mais j’ai exclu si grande quantité de diviseurs par démonstrations infaillibles, et j’ai de si grandes lumières, qui établissent ma pensée, que j’aurois peine à me dedire. I do not have an exact demonstration, but I have excluded so many divisors by infallible demonstrations, and I have such great insights which establish my thoughts, that I would have trouble telling myself otherwise.

Pierre de Fermat to Bernard Frénicle de Bessy, August (or early September?) 1640 [22]

Fermat would have had no difficulty finding the first four terms of the sequence F₀ to F₃ to be prime, but the gist of Fermat’s letter suggests he may have attempted trial division on at least F₄, and possibly F₅ also. If he did, it seems likely he made an arithmetical error when he came to the tenth 2kp + 1 trial division of F₅, and so missed the crucial further discovery that would have shattered his conjecture (note that here p is a power of 2 rather than a prime, so the 2kp + 1 form becomes k·2^m+1 + 1). Fermat also communicated this conjecture to Mersenne in the final letter we have from 1640, dated 25 December, as the first section of a lengthy missive with other subjects; Mersenne is of course now associated most closely with the sequence of 2^p–1 primes, although it perhaps should be noted that he also added to the list of suspect claims, since his list of exponents p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257 give rise to nine Mersenne primes and two composite numbers (since 2⁶⁷–1 and 2²⁵⁷–1 were subsequently factored) [42].

Before we leave 1640, we note that the third letter to Frénicle, which was copied completely while still extant, contained Fermat’s little theorem, though characteristically Fermat did not provide a proof:

Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n’appréhendois d’être trop long. And this proposition is generally true for all expressions and all prime numbers; of which I would send you the demonstration, if I were not afraid of going on too long.

Pierre de Fermat to Bernard Frénicle de Bessy, 18 October 1640 [22]

Unlike the more famous theorem colloquially known as belonging to Fermat that was also found to be wanting a proof, this theorem was proved relatively soon in 1736, by virtue of being a special case of Euler’s totient theorem. Euler, having previously announced in 1732 that F₅ had been shown composite by being factored, in the same lecture had also made some assertions about perfect numbers, and like Ibn Fallûs, Cataldi, and Mersenne before him, listed some results that were subsequently found to be erroneous: he gave the first eleven perfect numbers as corresponding to p = 1, 2, 3, 5, 7, 13, 17, 19, 31, 41, and 47 (however 2⁴¹–1 and 2⁴⁷–1 are not prime, and we do not consider 1 to be a prime) [20]. Euler subsequently proved the necessary condition of Euclid’s theorem on perfect numbers in 1747 (it is now known as the Euclid–Euler theorem), and proved 2³¹–1 prime by 1772 [21].

3. Édouard Lucas and the development of primality tests

One of Édouard Lucas’ main contributions to number theory was the investigation of sequences, and the use of specially chosen sequences to prove primality or compositeness for numbers of particular forms. In late 1875 (and announced on 10 January 1876 [37]) Lucas used a sequence to prove the Mersenne number M₁₂₇ = 2¹²⁷ – 1 was prime; Lucas’s sequences form the basis for the Lucas–Lehmer test. M₁₂₇ was the largest known prime number at the time, and was only eclipsed by a larger prime 75 years later [35]. The following year Lucas turned his attention to the Fermat numbers, finding a sequence that would give a congruence to zero modulo F_m if F_m is prime [37]. Lucas’s sequence for F_m, m > 1, requires n = 2^m – 1 terms starting with an initial seed of H₁ = 3, and the recurrent term is defined as

H_x+1 = 2 · H_x² – 1, x ≥ 1.

The sequence Lucas proposes is a subsequence of the half companion Pell numbers (i.e., the sequence obtained by multiplying each term of OEIS A002203 by a half), which have a general form into which we substitute n = 2^x, x ≥ 1, since we only need the subset of terms from the sequence where n is a power of 2 (and the previous identity only holds for even terms of the companion Pell sequence):

H_x = ½[(1 + √2)^{2^x} + (1 – √2)^{2^x}]

The subsequence starts H₁ = 3, H₂ = 17, H₃ = 577, H₄ = 665,857, H₅ = 886,731,088,897, … requiring repeated squarings, multiplication and subtraction modulo to the Fermat number, until the n^th = 2^m – 1 term is reached, one of which is claimed by Lucas to be divisible by F_m if F_m is prime. (The first x terms of the H_x subsequence also appear as factors of the Pell numbers U_y (2, –1), where y is any power of 2 greater than 2^x.) Lucas observed that trial factoring on F₆ would potentially take three thousand years of calculations, whereas his method would generate a sequence of around sixty large numbers that might take thirty hours to calculate, although the process would not provide factors if the number were discovered to be composite. His notice also mentioned that he was performing the required calculations on F₆ and F₇.

Lucas’s method was almost immediately improved upon by Théophile Pépin, who constructed a simpler sequence and proved that it is also conclusive in determining the primality of Fermat numbers in a theorem that we now refer to as the Pépin test [48]. This follows on from Lucas’s idea of a converse to Fermat’s little theorem, which gives rise to a probabilistic primality test: if the theorem’s result a^p–1 ≡ 1 (mod p) holds for an exponent p that we do not know to be prime or composite otherwise, then we can say p is probably prime, whereas if it does not, then p is definitely composite; here the special form of Fermat numbers allows a choice of the base a that is always coprime:

P_n = α^½(F_n–1) ≡ –1 mod F_n, if and only if F_n is prime, n > 1,

where α is the carefully chosen base so that the Jacobi symbol (α/F_n) = –1. Pépin initially proposed α = base 5, however following the observation of François Proth that many bases fulfil this criterion, the typical base used for the Pépin test is base 3. (Using a small Fermat number such as F₂, it is relatively easy to confirm Pépin’s test with mental arithmetic by evaluating α⁸ mod 17 in several bases, such as α = 3, 5, 6, 7, 10, and 12.) Pépin’s test is an improvement computationally as it only requires successive squarings modulo the Fermat number, rather than repeated steps of squaring alternating with multiplication and subtraction (even though each intermediate step is relatively straightforward). At this point we may use the first composite Fermat number F₅ as a worked example, since the calculations involve values that are at most 20-digit integers and are easily checked, and introduce Gostin’s cofact program to verify the result.

F₅ = 2^2⁵ + 1 = 4,294,967,297

P₅ = 3^½(F₅–1) mod F₅ = 3^{½(4,294,967,296)} mod F₅ = 3^{2,147,483,648} mod F₅ = (3²)^{1,073,741,824} mod F₅ = (9²)^536,870,912 mod F₅ = (81²)^268,435,456 mod F₅
= (6,561²)^134,217,728 mod F₅ ≡ (43,046,721² mod F₅)^67,108,864 ≡ (3,793,201,458² mod F₅)^33,554,432 ≡ (1,461,798,105² mod F₅)^16,777,216
≡ (852,385,491² mod F₅)^8,388,608 ≡ (547,249,794² mod F₅)^4,194,304 ≡ (1,194,573,931² mod F₅)^2,097,152 ≡ (2,171,923,848² mod F₅)^1,048,576
≡ (3,995,994,998² mod F₅)^524,288 ≡ (2,840,704,206² mod F₅)^262,144 ≡ (1,980,848,889² mod F₅)^131,072 ≡ (2,331,116,839² mod F₅)^65,536
≡ (2,121,054,614² mod F₅)^32,768 ≡ (2,259,349,256² mod F₅)^16,384 ≡ (1,861,782,498² mod F₅)^8,192 ≡ (1,513,400,831² mod F₅)^4,096
≡ (2,897,320,357² mod F₅)^2,048 ≡ (367,100,590² mod F₅)^1,024 ≡ (2,192,730,157² mod F₅)⁵¹² ≡ (2,050,943,431² mod F₅)²⁵⁶
≡ (2,206,192,234² mod F₅)¹²⁸ ≡ (2,861,695,674² mod F₅)⁶⁴ ≡ (2,995,335,231² mod F₅)³² ≡ (3,422,723,814² mod F₅)¹⁶
≡ (3,416,557,920² mod F₅)⁸ ≡ (3,938,027,619² mod F₅)⁴ ≡ (2,357,699,199² mod F₅)² ≡ 1,676,826,986² mod F₅
≡ 10,324,303 mod 4,294,967,297 ≢ –1 mod F₅

Similar to Lucas’s sequence we generate a succession of interim residues of squarings modulo to the Fermat number, where we eventually want the ultimate term to be congruent to –1. Alas for Fermat’s conjecture, it is not congruent for m = 5. Gary B. Gostin, who has discovered roughly one Fermat factor every six months (on average) for the last four and a half decades, has written a small executable named cofact, which uses the GMP and gwnum maths libraries for performing modular multiplication operations on large numbers (by which we mean, numbers up to a billion binary digits in size) which we will use ubiquitously hereafter to replicate results of Pépin tests [69]. The result generated by cofact confirms F₅ is composite by showing the final residue to various moduli that are larger than F₅, which we will discuss in detail later at section 6. For now it is sufficient to observe that the three numbers in decimal all replicate our worked calculations:

Command line: cofact 5 

Testing F5 for primality using the Pepin test
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x00000000009D894F 10324303 10324303 10324303
F5 is composite

Lucas is on the record later in 1877 as having conceded that Pépin’s method was simpler than his own, and reported that he had used either Pépin’s or more likely his own sequence to find F₅ and F₆ composite [38]. Perhaps due the greater length of the calculation, he does not appear to have followed through on determining the character of F₇. So we coded Lucas’s sequence [37] and duly found that the residues modulo F₅, F₆, and F₇ were indeed non-zero, but the behaviour of the sequence is also somewhat contrary to Lucas’s initial article, where Lucas specified n = 2^m–1 terms of his sequence needed to be evaluated; the later 1877 revision clarifies matters by specifying that a Fermat prime must divide one of the terms H_n between n = 2^m–1 and 2^m – 1 [38]. The Fermat prime F₂ divides the second term H₂ as expected (here n = 2^m–1), the next prime F₃ divides the fifth term H₅, and the largest Fermat prime F₄ divides the eleventh term H₁₁. If H₀ = 1 is added to the subsequence as a ‘first’ term, then we reach agreement with the revised article, where Lucas refers to F₂, F₃, and F₄ dividing the third, sixth, and twelfth terms, each of which precede the fourth, eighth, and sixteenth terms of the sequence. Unhelpfully there are no more Fermat primes available beyond F₄ for further comparison [38].

If a Fermat number is composite, Lucas’ subsequence exhibits cyclic behaviour which suggests divisibility is never achieved. For F₅, the residues of H_n mod F₅ cycle through the same 4,362 values after reaching H₇, every successive term alternating between being congruent to 181 mod 641 or 139 mod 641. The residues modulo F₆ also cycle after reaching H₈, returning after another 8,551,088,856 further terms, so that H₈ ≡ H_{8,551,088,864} ≡ 13,183,403,781,156,872,930 (mod F₆). No larger composite Fermat numbers up to F₂₄ exhibited a cycle in the first million terms of Lucas’s subsequence (the residues modulo F₇ and F₈ did not appear to repeat in the first hundred billion terms), however many cycles were evident when checking divisibility of the same sequence by k·2ⁿ+1 factors of F_m with small k values. The most piquant example of this was finding the only known factor of F₂₃ divides H₂₃, but the Fermat number F₂₃ itself does not; after one more term of the subsequence all following terms are congruent to 1 modulo 167,772,161.

By contrast the Pépin test is unambiguous and as we will see later at section 7, has a useful extension.

F₆ was factorised for the second time a few years later in 1880 by Fortuné Landry [34] (it had been factored some two decades earlier by Thomas Clausen, however the result was confined to a private letter to Carl Friedrich Gauss that went unnoticed until 1964 [2]), and Landry did not elaborate his method; H. C. Williams’ article [65] provides some detective work to establish how a task that Lucas had estimated to require three millennia might have been possible to conclude in under three years. The final residues from Lucas’s calculations do not appear to have been published to allow these to be checked, so the first results we may verify are found at the beginning of the twentieth century.

4. … and the number was, 110,780,954,395,540,516,579,111,562,860,048,860,420.

Fermat numbers become very large, very quickly. Fermat was possibly unlucky not to obtain the factorisation of F₅, whereas Euler was extremely lucky that he found the factor 641 with just the tenth possible value of k, not all of which would have need to have been tested by trial division if divisors (64k + 1) were observed to be composite rather than prime. The largest possible k smaller than the square root of F₅ after sieving out composites is 1,017; note that Euler probably would not have known Lucas’s modification given below, which reduces the number of 209 64k+1 primes to be tested to 99 128k′+1 primes.

k 64k+1 k′ 128k′+1    Character

1 65 composite

2 129 1 129 composite

3 193 prime

4 257 2 257 prime = F₃; no Fermat number can divide another Fermat number (Goldbach’s theorem)

5 321 composite

6 385 3 385 composite

7 449 prime

8 513 4 513 composite

9 577 prime

10 641 5 641 prime divides F₅

… … … …

1,008 64,513 504 64,513 prime

… … … …

1,017 65,089 prime

… … … …

1,022 65,409   511   65,409 composite largest value of k′ for smaller factor, 128k′+1 < √F₅

1,023   65,473 composite largest value of k for smaller factor, 64k+1 < √F₅

F₆ is a 20-digit number that was factored by manual arithmetic, twice, in the nineteenth century; here the largest possible k for a maximal smaller factor is 33,554,427. So trial division was not a viable method to proceed with the next smallest Fermat number of unknown character, F₇, which is a 39-digit number; a smaller factor that happened to be just less than the square root would have k ~ 2⁵⁶. While Lucas had also discovered in 1877 [37,39] that the k·2^m+1 + 1 form of Fermat divisors always includes one additional power of 2 (i.e. k′·2^m+2 + 1), that only reduces the maximal k′ for F₇ by one power of 2 to ~ 2⁵⁵; when it was eventually discovered in 1970, the smaller factor had k well towards the maximum size possible, ~ 2^46.727.

So the most practical way forward for determining the nature of F₇ was to carry out the Pépin test for primality. In 1905, this was achieved by Alfred Edward Western in the United Kingdom [64], and James Caddall Morehead in the United States [43], each more or less without knowledge of the other party. Where Mersenne numbers are a single exponential, and Fermat numbers a double exponential, the Pépin test is a triple exponential: if we were unable to reduce the calculation modulo F₇, then the test would seemingly require the evaluation of 3 to the power of half of 2 to the power of 2 to the power of 7, or

P₇ = 3^{170,141,183,460,469,231,731,687,303,715,884,105,728}

However such a gigantic number does not need to be calculated; starting with the number 3 we merely need to recursively square the value 127 times, and whenever the result of a squaring exceeds F₇ we reduce it to the smallest positive congruence modulo F₇. Lucas’s 1877 estimate of thirty hours of calculation to determine the composite character of F₆ permits a similar estimate of perhaps 240 hours minimum for F₇. Evaluating P₇ involves twice as many squarings and reductions modulo F₇, and the numbers being calculated are roughly one squaring larger than all of the intermediate numbers generated for F₆: the square of a 39-digit number can result maximally in a 78-digit number.

Morehead was the first to publish a complete residue, with the foresight that such a complex calculation could not simply be announced as a given truth without being subject to verification, however tedious that might be to perform; his result was:

P₇ ≡ 110 780 954 395 540 516 579 111 562 860 048 860 421 mod F₇.

Western’s brief note to the London Mathematical Society notified the same result, but without producing a final residue. He had used a method where he needed to evaluate only 119 modular squarings instead of 127, an idea which would be reused later for testing F₈ and which we will examine below. The cofact executable returns the following results, where we have added a custom flag to output the entire residue:

Command line: cofact -v 7 
R = 110780954395540516579111562860048860420
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x95984E80E902C504 3909272836 44591026080 5799525263
F7 is composite

The reader seeing that Morehead’s residue P₇ finished with the final five digits 60421, whereas cofact’s value R finishes with 60420, might be tempted to think something is awry, but there is no problem. Morehead’s statement of the Pépin test added 1 to each side of the equation, so that

P₇ = 3^½(F₇–1) + 1 ≢ 0 mod F₇,

which is one greater than the number calculated by cofact. Morehead noted, “A similar computation for F₈, if practicable at all, would involve eight times the labor of the computation for F₇.”

5. Morehead and Western redux

Faced with a much larger calculation, Morehead and Western decided to join forces to attack the Pépin test of F₈. They armed themselves with eight-digit mechanical calculators and a ten-digit arithmometer, and split the work between them: Western evaluated the first 126 squarings to reach 3^2¹²⁶ mod F₈, and then Morehead took over for the next 120 squarings [44]. Morehead and Western had contrived a scheme where they needed only to evaluate as far as the 2²⁴⁶th power of 3 to be sure P₈ ≢ –1 (mod F₈).

They observed 2^{2^m} also is congruent to –1 modulo F_m to obtain an equation

3^{2^{(2^m–m–2)}} ≡ ± 2^y(2^{2^m–1} ± 1) mod F_m, where 0 ≤ y ≤ 2^m–1.

This indicative interim residue can be calculated for the two largest Fermat primes to be congruent to 136 mod F₃ and 8,224 mod F₄, which both satisfy this identity for y = 3 and 5 respectively, both with positive parity of signs (by contrast, the interim residue 2,995,335,231 mod F₅ is found to be incongruent). Morehead and Western’s interim residue for F₈ was found to be

( 107 2093 3158 0550 8180 4331 6350 5866 1999 4098 )x

+ ( 34 1778 3881 0697 6545 8021 2127 5588 1034 4254 ),

where x = 2¹²⁸. At this point, Morehead and Western only needed to check division by (x ± 1) and confirm the remainder was non-zero and the quotient (or its complement mod F₈) was not a power of 2; by trivial inspection, F₈ is composite. We may also evaluate this immediately as

3^2²⁴⁶ ≡ 36,481,445,106,241,549,041,743,091,260,464,972,368,896,526,668,121,542,479,669,252,869,581,546,330,942 mod F₈,

as well as obtaining the Pépin test residue from Morehead and Western’s interim value by performing nine more squarings modulo F₈,

P₈ ≡ 5,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 (mod F₈) ≢ –1 (mod F₈).

Once again we will use a special flag when running cofact to print out the interim and final residues, which confirms both the correctness of the calculations and Morehead and Western’s method for establishing the compositeness of F₈:

Command line: cofact -iv 8

R = 36481445106241549041743091260464972368896526668121542479669252869581546330942
Interim Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0xED8911F2F2461B3E 12654615358 46029482672 7439654090

R = 5864545399742183862578018016183410025465491904722516203269973267547486512819
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x6507E50AC84D66B3 46310188723 35403253324 30627284506
F8 is composite

6. The computer era begins: Robinson, Selfridge, Hurwitz, and Paxson

The era of manual calculation yielded the factoring of F₅ and F₆, the compositeness results of F₇ and F₈, and a variety of factors discovered by trial division, so that F₉, F₁₁, F₁₂, F₁₅, F₁₈, F₂₃, F₃₆, F₃₈, and F₇₃ were also known to be composite; therefore the smallest Fermat numbers of unknown character were F₁₀, F₁₃, and F₁₄. On 30 January 1952, Raphael M. Robinson used the National Bureau of Standards Western Automatic Computer, known as SWAC, at the Institute for Numerical Analysis in Los Angeles to run a program he had written to investigate Mersenne numbers by implementing the Lucas–Lehmer test (with assistance from both D.H. and Emma Lehmer). The success of his program was demonstrated almost immediately by the discovery of the thirteenth and fourteenth Mersenne primes M₅₂₁ and M₆₀₇ before the day was out. Three more Mersenne primes were discovered by Robinson later in the year. [35,52]

The Lucas–Lehmer program was rewritten to run the Pépin test on F₁₀, which was found to be composite on 4 February. Robinson also confirmed Morehead and Western’s results for F₇ and F₈. Emma Lehmer, besides converting various residues from hexadecimal to decimal for comparison, also recoded the program the following January to verify Robinson’s result. Robinson published the full residue in 1954 as 254 hexadecimal digits (29 36-bit words, with u, v, w, x, y, and z as the additional hex digits):

                 8x 4z258xu89 uw71y6w35 9z1vyy4u5 498v2v7v7 
55y9wy98v 6yx3yy0x4 00u07877w 2866316zu 85wy92558 3y201x7x0 
04w1zv076 yu292wxx4 0502v7567 226047037 308u12z32 887vyxu4x
51w50169z 6815w50u1 0wy653448 v953xy0w6 8uv4492z2 v1u564ux9
494x25wv7 wux26uuvw 4w5x12730 622y6z435 5xy035xx2 8798y8098

The verbose flag for cofact prints the upper 64 bits and the lower 128 bits of the Pépin residue, which consists of 16 64-bit words, and can be seen to be identical with the bolded portion of Robinson’s SWAC residue by exchanging (u…z) with (a…f):

Command line: cofact -v 10 
Pepin residue:  length = 16, 008d4f258da89ac7 ... 12730622e6f4355d e035dd28798e8098

Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0xE035DD28798E8098 36399120536 54182679152 28022031617
F10 is composite

Robinson speculated that compared with the difficulty of evaluting the Pépin test for the next Fermat number of unknown character, F₁₃ = 2^8,192+1, “[i]t would probably be considerably easier to find some additional factors of Fermat numbers by trial.” Robinson could speak from experience: on 15 August 1953 John L. Selfridge had used SWAC to find 11,131·2¹²+1 divided F₁₀ (and rendered his compositeness test obsolete) after having first discovered another factor 1,575·2¹⁹+1 divided F₁₆ the previous day [52,54]. Robinson and Selfridge found another 20 factors in 1956 and 1957 [53] before the next compositeness test was performed on F₁₃.

In December 1960 G.A. Paxson used 6 hours and 17 minutes of machine time on an IBM 7090 mainframe to determine F₁₃ was composite [47]; he had also replicated the Morehead and Western, and Robinson results, and had commandeered about half of the 49½ hours of computing time required to test F₁₄ before he was overtaken by Alex Hurwitz and John Selfridge, with whom he successfully compared interim results [29,55].

It is to Selfridge and Hurwitz’s 1964 paper that we have a full set of matching results that also set a standard for later publications. Their own IBM 7090 was observed to occasionally make errors, so they sought a means of checking their computations as well as a compact form for comparing results made by other researchers, and they hit upon using a triplet of different small integer moduli to reduce the full residue: 2³⁶ = 68,719,476,736; 2³⁶ – 1; and 2³⁵ – 1 = 34,359,738,367. The first member of the triplet thus reproduces the 36 least significant bits of the full residue, while the other two function as checksums, by decreasing the likelihood that an incorrect calculation could masquerade as a correct one: for two different values to each record identical Selfridge–Hurwitz residues by chance is roughly 1 in 2^(36+36+35). Hurwitz and Selfridge, having obtained confirmatory results on five Fermat numbers including F₁₀, also provided as a gift for future reseachers the residue from the n = 20^th squaring (out of 131,071 total) for testing the next Fermat number of unknown character, F₁₇:

m n P_m mod 2³⁶ P_m mod 2³⁶ – 1 P_m mod 2³⁵ – 1

7 127 035100542404 514165207640 053153335617

8 255 531023263263 407614543114 344141643032

13 8,191 607301005536 611677367012 031455470517

14 16,383 622476273512 016631677043 161031465216

17 20 176536764625 415751561367 155276133751

These results were formatted in octal rather than decimal, so again we modify cofact’s output.

Command line: cofact -o 7 
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x95984E80E902C504   3909272836  44591026080   5799525263
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x95984E80E902C504  35100542404 514165207640  53153335617 (octal)
F7 is composite
Command line: cofact -o 8
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x6507E50AC84D66B3  46310188723  35403253324  30627284506
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x6507E50AC84D66B3 531023263263 407614543114 344141643032 (octal)
F8 is composite
Command line: cofact -o 13
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0xD79356EC3B040B5E  52529728350  52864871946   3434508623
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0xD79356EC3B040B5E 607301005536 611677367012  31455470517 (octal)
F13 is composite
Command line: cofact -o 14
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0xCC52BC3C94F9774A  54038984522   1986493987  15173315214
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0xCC52BC3C94F9774A 622476273512  16631677043 161031465216 (octal)
F14 is composite
Command line: cofact -io 17
Iteration:        20
Interim Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x5EA8C873F57BE995  17003440533  36232946423  14679586793
Interim Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x5EA8C873F57BE995 176536764625 415751561367 155276133751 (octal)

The calculation of Pépin’s test on F₁₇ requires eight times as many modular squarings on numbers which are themselves larger by three squarings. Compared with 42 hours of machine time taken for the Pépin test of F₁₄, Selfridge and Hurwitz estimated F₁₇ would demand 128 machine weeks on an IBM 7090 (or 512 times the amount of computation). It seems that no one took up the challenge, as Hallyburton & Brillhart’s 1975 paper [28] lists the character of F₁₇ as an open question; a question which was soon rendered moot by the discovery of the smallest factor by Gary Gostin in May 1978 [25].

7. Hiromi Suyama and cofactor compositeness tests

By the end of 1961 the ten Fermat numbers between F₇ and F₁₆ were all known to be composite, though only four had no known factors; the characters of the six cofactors were unknown, and of sufficient size to more likely be composite rather than prime. In 1967 John Brillhart tested the two smallest cofactors, c₁₄₈ | F₉ and c₂₉₁ | F₁₀, on an IBM 7094 at the Bell Telephone Laboratories in Holmdel, New Jersey, finding both to be composite (here the subscript on a cofactor c indicates a number of 148 or 291 decimal digits respectively, and we also specify which Fermat number the cofactors divide into); his 1975 paper co-authored with John C. Hallyburton Jr does not specify what test was used to establish non-primality [28]. Gostin’s 1980 discovery paper for the smallest factor of F₁₇ also relates results of further late 1970s tests by Samuel S. Wagstaff Jr which confirmed the compositeness of c₆₀₆ | F₁₁, c_1,202 | F₁₂, and c_2,454 | F₁₃ [25].

We might conceptualise the progress of investigation into a particular Fermat number as following a sequence of steps, with some steps possibly being omitted due to circumstance:

Fermat number has unknown character → Pépin test → ( find new factor → test cofactor; if composite, continue search ↩︎) → if cofactor is prime, then factoring is complete

The discovery of small factors generally outpaced the computation power required to evaluate the Pépin test: of the 26 smallest composite Fermat numbers only eight were first shown composite with this method. However, as time went on the ability to run large computations on more modest hardware allowed some of these investigations to be carried out on microcomputers. Hiromi Suyama began investigating Mersenne and Fermat numbers in 1980 using a microcomputer and published his compositeness test of c_9,856 | F₁₅ as a preliminary abstract in 1984 [56]. Suyama took the small 10-digit factor p₁₀ of F₁₅ and evaluated A = p₁₀^F₁₅–1 mod F₁₅, and B = p₁₀^p₁₀–1 mod F₁₅. Finding A ≠ B he applied Fermat’s theorem to conclude the F₁₅/p₁₀ cofactor was composite.

This cofactor test is similarly expensive in computation to the Pépin test, so Hendrik W. Lenstra Jr observed it can be modified as an extension of the Pépin test by choosing the base 3 [31]. If this is the case

A_m = 3^F_m–1 mod F_m = P_m² mod F_m, where P_m is the base 3 Pépin residue;

B_m = 3^Q–1 mod F_m, where Q = Πp_i is the product of the known prime factors p_i of F_m.

The character of the cofactor C can be determined by evaluating S_m = (A_m – B_m) mod C, where

S_m { ≡ 0, if C is prime (or probably prime to the base 3^Q),
≢ 0, if C is composite.

Since we previously used F₅ as a worked example, we may recapitulate to demonstrate the Suyama test with small numbers. Imagine we did not know the character of the F₅/641 cofactor. Then:

A₅	= 3^{4,294,967,297–1} mod F₅ ≡ 10,324,303² mod F₅ ≡ 3,029,026,160 mod F₅
B₅	= 3^641–1 mod F₅ = (3⁵)¹²⁸ mod F₅ = (243²)⁶⁴ mod F₅ = (59,049²)³² mod F₅
	≡ (3,486,784,401² mod F₅)¹⁶ ≡ (2,154,247,120² mod F₅)⁸
	≡ (2,071,276,438² mod F₅)⁴ ≡ (3,338,530,402² mod F₅)²
	≡ 151,033,060² mod F₅ ≡ 1,581,736,088 mod F₅
S₅	= (3^{4,294,967,296} – 3⁶⁴⁰) mod 6,700,417
	≡ (3,029,026,160 – 1,581,736,088) mod 6,700,417 = 1,447,290,072 mod 6,700,417
	≡ 0 mod 6,700,417

Thus the cofactor 6,700,417 obtained by dividing F₅ by 641 is prime. With cofact we can reproduce the A₅, B₅, and (A₅ – B₅) mod C results:

Command line: cofact 5 641

Pepin Residue mod 2^64 2^35-1 2^36-1 2^36: 0x00000000009D894F 10324303 10324303 10324303
F5 is composite
Testing the F5 cofactor for primality using the following known factors: 641
Cofactor (7 digits): 6700417
A Residue mod 2^64 2^35-1 2^36-1 2^36: 0x00000000B48B4570 3029026160 3029026160 3029026160
B Residue mod 2^64 2^35-1 2^36-1 2^36: 0x000000005E476098 1581736088 1581736088 1581736088
(A-B) mod C Residue mod 2^64 2^35-1 2^36-1 2^36: 0x0000000000000000 0 0 0
F5 cofactor is prime!

Note that we could have run cofact giving it the larger prime factor, in which case we obtain a different B′₅ quantity; however (A₅ – B′₅) mod C still gives the same result as Suyama’s test confirms both factors are (probably) prime.

Testing the F5 cofactor for primality using the following known factors: 6700417
Cofactor (3 digits): 641
A Residue mod 2^64 2^35-1 2^36-1 2^36: 0x00000000B48B4570 3029026160 3029026160 3029026160
B Residue mod 2^64 2^35-1 2^36-1 2^36: 0x000000005643E4D9 1447290073 1447290073 1447290073
(A-B) mod C Residue mod 2^64 2^35-1 2^36-1 2^36: 0x0000000000000000 0 0 0
F5 cofactor is prime!

If a cofactor is composite, there is a possibility it is a prime power, equal to p^k for some value of p and k > 1. There are a number of unproven conjectures about Fermat numbers, one of which is that no Fermat number has a factor of a prime raised to a power k > 1; if this conjecture is false, then it is nevertheless thought relatively unlikely that very many Fermat numbers have prime power factors. To test whether a composite cofactor C is a prime power, one step would be to compute gcd(a^C – a, C) for some suitable value a, which should yield 1 if C is not a prime power. If the greatest common divisor is not 1, then C would be divisible by the gcd.

Having gone to the effort of a Pépin test however, the Suyama test proves its usefulness again. If Q again represents the product of all known prime factors of F_m, or in other words F_m = Q · C, then by substituting a = 3^Q

gcd(a^C – a, C) = gcd((3^Q)^C – 3^Q, C)
= gcd(3^F_m – 3^Q, C)
= gcd(3^F_m–1 – 3^Q–1, C), since F₀ = 3 cannot be a factor for m ≥ 1 (Goldbach)
= gcd(A_m – B_m, C),

where A_m and B_m are the corresponding values from the Suyama test given above. The Suyama test therefore can prove a cofactor to be composite, and detect whether the cofactor is a prime power. None of the cofactors to date have yielded anything other than gcd(A_m – B_m, C) = 1, however.

Through the 1980s and 1990s the increase in computation power continued to be applied to primality tests of larger Fermat numbers and their cofactors:

m Year Cofactor Prover

15 1984 c_9,856 H. Suyama [56]

12 1986 c_1,187 R. J. Baillie [61]

15 1987 c_9,840 H. Suyama [57]; R. J. Baillie [61]

16 1987 c_19,720 R. J. Baillie [61]

17 1987 c_39,444 R. J. Baillie [32]

11 1988 c₅₈₄ R. P. Brent [6]

11 1988 p₅₆₄ F. J. Morain [6]

18 1990 c_78,907 D. V. & G. V. Chudnovsky [62]

13 1991 c_2,436 A. K. Lenstra, W. Keller [30]

13 1991 c_2,417 R. E. Crandall [14]

19 1993 c_157,804 R. E. Crandall, J. Doenias, C. Norrie, J. Young [15]

21 1993 c_631,294 R. E. Crandall, J. Doenias, C. Norrie, J. Young [15]

13 1995 c_2,391 R. P. Brent [6,8]

16 1996 c_19,694 R. P. Brent & R. E. Crandall [8]

15 1997 c_9,808 R. P. Brent & R. E. Crandall [8]

18 1999 c_78,884 R. E. Crandall [32]

Crandall, Doenias et al. in their 1995 paper [15] explicitly stated their use of the Suyama cofactor test and published residues which we will examine below in the context of the three Pépin tests on F₂₀, F₂₂, and F₂₄, which were the next three Fermat numbers of unknown character.

8. The twentieth, twenty-second, and twenty-fourth Fermat numbers are composite

Suyama’s test on the c_9,840 | F₁₅ cofactor is described as having taken 100 hours on a microcomputer in 1987 [63], following Gostin’s discovery of a new factor. Several months earlier Jeff Young and Duncan A. Buell had run the Pépin test on F₂₀ using a Cray-2 supercomputer at the Supercomputing Research Center in Lanham, Maryland, taking about 10 days of computation to find it composite. They verified their work on a Cray X-MP belonging to Cray Research in Mendota Heights, Minnesota, taking 82 hours [68]. As they remarked in their 1988 paper,

… this 10-day computation on a supercomputer may well be the largest computation ever performed whose result is a single bit answer. Never have so many circuits labored for so many cycles to produce so few output bits.

Had F₂₀ been prime, the most significant bit (representing 2^2²⁰) would have have been a one, and all the remaining bits would have been zeroes; instead the result obtained was a zero followed by a string of 2²⁰ more or less random 1s and 0s. Their residues in octal were:

P₂₀ ≡ 175517362761 (mod 2³⁶),
P₂₀ ≡ 411337412531 (mod 2³⁶ – 1),
P₂₀ ≡ 161572365764 (mod 2³⁵ – 1).

As a ‘sanity check’ they also confirmed their program reproduced the same residues Selfridge and Hurwitz had published in 1964; likewise, we can use cofact to double check Young and Buell’s Cray Fortran programming:

Command line: cofact -o 20
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x78791573ED3DE5F1 175517362761 411337412531 161572365764 (octal)
F20 is composite

The next smallest Fermat number of unknown character was F₂₂, which Richard E. Crandall, Joshua Doenias, Chris Norrie, and Jeff Young investigated in 1993 [15], using an Amdahl 5995M model 4550 mainframe computer for the primary run of the Pépin test; Norrie and Young used two different methods for verifying this result. At particular ‘signpost’ values of the modular squaring loop the mainframe would save out interim residues, say at iteration values a and b so that b – a is a relatively small interval such as a thousand; these interim residues could then be tested on a fleet of slower workstations to verify that the required number of squarings starting at a would reproduce the correct residue at b. Something like this technique was also used to verify successive residues on a Cray supercomputer.

Sanity checks were run by duplicating Pépin tests not only on the previously investigated Fermat numbers, but on every composite Fermat number up to F₂₂:

m P_m mod 2³⁶ P_m mod 2³⁶ – 1 P_m mod 2³⁵ – 1

5 10324303 10324303 10324303

6 8845352501 9017941414 9190530327

7 3909272836 44591026080 5799525263

8 46310188723 35403253324 30627284506

9 19661770102 54966870189 28173182079

10 36399120536 54182679152 28022031617

11 66666487080 44928212591 3934743084

12 64546579219 3387502849 5300454051

13 52529728350 52864871946 3434508623

14 54038984522 1986493987 15173315214

15 7124011679 42435904961 14110954287

16 24695037109 65390296136 173595305

17 14726733277 2770550506 14982977589

18 46106404592 14070013587 10874364700

19 22254317980 58676148574 6407009455

20 16865158641 35626292569 15265819636

21 22442941248 300257643 30981963597

22 973723434 8733349067 12323430823

The observant reader will notice these are decimal residues rather than hexadecimal or octal. These were all confirmed by cofact (cf. Appendix 1 below) with the exception of the P₁₂ mod 2³⁵ – 1 residue, which appears to be missing a digit 5 at the start of the number, and which is otherwise identical. Similarly to how Morehead and Western each discovered their work to have been replicated by the other in 1905, Crandall, Doenias et al. learned about nine months afterwards that their work had been independently verified by a couple of researchers in Brazil, Vilmar Trevisan and João B. Carvalho, with whom they shared S–H residues by email to confirm each other’s results were identical.

The Brazilian mathematicians Trevisan and Carvalho had access to a Cray Y-MP/2E, which had extensive amounts of idle time overnight as the Brazilian Supercomputing Center was then newly created, and the amount of computing time had not yet been booked to capacity; so the calculation of the Pépin test would run as low priority batches, usually computing 6,000 or 8,000 squarings before saving an interim residue to storage which would provide the starting point for the next batch. Their paper, also published in 1995, includes S–H residues for 13 of these interim values, along with the final 4,194,303^rd squaring (which of course, was the same as given above) [58].

n P₂₂ mod 2³⁶ P₂₂ mod 2³⁶ – 1 P₂₂ mod 2³⁵ – 1

126000 14541047264 62070375509 27381595983

354000 45744331640 37262695986 30266592884

486000 24041343749 49018090515 1797017786

790000 66015459363 57091562477 29124348244

1078000 41097905003 41183234167 18395262145

1430000 37800690011 17322513532 30657148115

1854000 13706770442 2076479040 105211355

2390000 39355539574 67554578594 23663736438

2718000 45076516494 67299003714 535858315

3046000 397350536 19533135442 15348306

3542000 10838294599 41096201992 14648574810

3838000 4342596189 27597863567 31241328256

4182000 49032769250 16910406249 26122490955

Command line: cofact -i 22 

Testing F22 for primality using the Pepin test
Iteration:    126000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x0E86FD2362B6C5E0 14541047264 62070375509 27381595983
Iteration:    354000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x3CF35A3AA6931B78 45744331640 37262695986 30266592884
Iteration:    486000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x7628D54598F9CB05 24041343749 49018090515  1797017786
Iteration:    790000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x00E09C6F5ED3F823 66015459363 57091562477 29124348244
Iteration:   1078000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x522EC83991A0436B 41097905003 41183234167 18395262145
Iteration:   1430000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x54C3A938CD18C15B 37800690011 17322513532 30657148115
Iteration:   1854000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0xE108BE3330FCB80A 13706770442  2076479040   105211355
Iteration:   2390000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x19E9171929C5E076 39355539574 67554578594 23663736438
Iteration:   2718000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x969AAEAA7EC50E8E 45076516494 67299003714   535858315
Iteration:   3046000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x7BF3514017AF1688   397350536 19533135442    15348306
Iteration:   3542000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x442A758286034047 10838294599 41096201992 14648574810
Iteration:   3838000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0xF5EA5E0102D6C25D  4342596189 27597863567 31241328256
Iteration:   4182000 /   4194303 Interim Residue mod 2^64 2^36 2^36-1 2^35-1: 0x966FB01B6A94AEE2 49032769250 16910406249 26122490955

Having run the Pépin test on F₁₉ and F₂₁, Crandall et al. also ran the Suyama test on the cofactors, publishing the main A_m and B_m results modulo C modulo 2¹⁶ rather than as Selfridge–Hurwitz residues. cofact produces the following Suyama S–H residues:

Command line: cofact -mu F19.proof 19 70525124609 646730219521
Testing the F19 cofactor for primality using the following known factors: 70525124609 646730219521 
Cofactor is 157804 digits long
A Residue mod 2^64 2^36 2^36-1 2^35-1: 0x449FBCA640B4FA27 26855406119 30933529616 405458041
A mod C Residue mod 2^64 2^36 2^36-1 2^35-1: 0xC3F3BED458A8CAE9 18667326185 5232651448 179782044
B Residue mod 2^64 2^36 2^36-1 2^35-1: 0xD47E9003E02D2D27 16645958951 8574767701 34097891288
B mod C Residue mod 2^64 2^36 2^36-1 2^35-1: 0x7F2FFA296E773815 40508012565 14890216756 28478244829
(A-B) mod C Residue mod 2^64 2^36 2^36-1 2^35-1: 0x613DE003EA7192D5 16818213589 23335948090 3487019629
F19 cofactor is composite, and is not a prime power (GCD of A-B, C = 1)

Command line: cofact -mu F21.proof 21 4485296422913
Testing the F21 cofactor for primality using the following known factors: 4485296422913 
Cofactor is 631294 digits long
A Residue mod 2^64 2^36 2^36-1 2^35-1: 0xA07023647D42B4D5 19281392853 11280367853 12351604643
A mod C Residue mod 2^64 2^36 2^36-1 2^35-1: 0x601BFDD97352A23A 40589500986 50838168773 3644444837
B Residue mod 2^64 2^36 2^36-1 2^35-1: 0xDA11FF47C9F2DBA7 33452907431 25506585220 5803823552
B mod C Residue mod 2^64 2^36 2^36-1 2^35-1: 0x45B0DC93C4999DC9 16183303625 31895836606 22284475692
(A-B) mod C Residue mod 2^64 2^36 2^36-1 2^35-1: 0x1A6B2145AEB90471 24406197361 18942332167 15719707512
F21 cofactor is composite, and is not a prime power (GCD of A-B, C = 1)

We have taken the further step to reduce both the A_m and B_m values modulo C to match Crandall, Doenias, Norrie, and Young’s results; their results are here tabulated with the cofact residues, reduced further to mod 2¹⁶:

m A_m mod C mod 2¹⁶ B_m mod C mod 2¹⁶ cofact A_m mod C mod 2¹⁶ cofact B_m mod C mod 2¹⁶

19 51945 14357 CAE9₁₆ = 51945 3815₁₆ = 14357

21 41530 40393 A23A₁₆ = 41530 9DC9₁₆ = 40393

The twentieth century was rounded out with Crandall teaming up with Ernst W. Mayer and Jason S. Papadopoulos, who showed F₂₄ to be composite with the Pépin test in 1999; their 2002 paper included some other results from the turn of the new millennium, announcing discoveries of the first factors of F₂₈ (Tadashi Taura, 1997) and F₃₁ (Alex Kruppa and Tony Forbes, 2001), which otherwise would have been considered to be the next smallest Fermat numbers of unknown character. The authors actually completed four separate runs, on account of one of the first runs having generated an incorrect result. This was shown to have been caused by restarting from an incorrectly-saved residue, the restart owing to a thunderstorm-induced power failure [16]. Besides the now traditional Selfridge–Hurwitz triplet, their result also includes a hexadecimal and decimal mod 2⁶⁴ residue:

modulus P₂₄ residue

2³⁶ 60450279532

2³⁶–1 68627742455

2³⁵–1 32898231088

2⁶⁴ 17311B7E131E106C₁₆
= 1671147165031731308₁₀

Command line: cofact 24 
Testing F24 for primality using the Pepin test
Pepin Residue mod 2^64 2^36 2^36-1 2^35-1: 0x17311B7E131E106C 60450279532 68627742455 32898231088
F24 is composite

Two of the successful Pépin tests utilised different hardware and software, running as fast as possible. The third run was a slow verification using integer multiplication rather than the typical fast Fourier transform implementations which involve rounding to the nearest integer. If the size of rounding errors ever exceed 0.5, this essentially wrecks the test, as if this happens a modular squaring obtains the wrong whole number; the only recourse is to return to a previously saved residue. Using integer multiplication is safe, but slow.

As a footnote to their paper, the 2,525,215-digit cofactor of F₂₃ was also tested and verified using Pépin/Suyama in November 2000 and found to be composite, but residues were not published. At the time of publication, Crandall, Mayer, and Papadopoulos described the next smallest Fermat number of unknown character as “the 8-gigabit colossus F₃₃”, which over 20 years later still remains inscrutably undetermined.

9. Enter the GIMPS

In 1996 George F. Woltman began the Great Internet Mersenne Prime Search, a distributed computing project that has discovered the seventeen largest and most recently-found Mersenne primes over the last twenty-seven years. Woltman’s software combines a general large maths library called gwnum (which cofact utilises) and an executable called mprime (for command line operation) or Prime95 (using a graphical user interface) for obtaining work units to calculate. The work units are distributed from a central server called PrimeNet, which coordinates the assignment and publishing of results. At the time of writing GIMPS has tested over two million Mersenne numbers for primality, so that every unfactored Mersenne number with exponent below 113 million has been tested at least once, and over one and a quarter million of these Mersenne numbers with exponents below 65 million have been verified composite. A vast number of Mersenne numbers have also been excluded from primality testing by trial factoring.

Woltman’s mprime software has gradually evolved to support various factorisation methods such as P–1 and P+1 factorisation, and the elliptical curve method, as well as the ability to apply Pépin’s test to the smaller Fermat numbers. Over 2009 to 2011 four new Fermat factors were found with mprime, as well as a large factor of F₁₂, by contributors to Woltman’s GIMPS project. David Bessell in Tasmania discovered factors of F₁₉, F₂₂, and F₁₇; Tapio Rajala in Finland discovered the first known factor of F₁₄, and Michael Vang in the United States discovered the sixth known factor of F₁₂, though this last result used the customised GMP-ECM package, rather than mprime.

In each case the new cofactor resulting from the discovery was found to be composite by GIMPS contributors soon after the announcement of the factor, with a variety of tests including the Suyama test. In addition the question of the nature of the cofactors of F₂₅ and above was raised and investigated. Shoichiro Yamada in Japan performed a Fermat–Euler test on the 10,100,482-digit cofactor of F₂₅ in 2009, finding it composite without giving a residue. His result was verified by Andreas T. Höglund in Denmark by means of a probable prime test using Woltman’s mprime, which Höglund followed up by similar computations for the cofactors of F₂₆ and F₂₇, finding each composite.

m Date    Cofactor Residue mod 2⁶⁴ Prover(s)

19   17 July 2009 c_157,770 C61CCF4C8ABEF914   J. R. King.; A. Kruppa; G. Childers et al. [66]

25 23 July 2009 c_10,100,842 44BFC8D231602007 S. Yamada (Fermat–Euler test) [66]; A. T. Höglund [66]; and in 2022, E. W. Mayer [41]

26 3 Aug 2009 c_20,201,768 6C433D4E3CC9522E A. T. Höglund [66]; and in 2022, E. W. Mayer [41]

14 3 Feb 2010 c_4,880 (no residue given) W. B. Lipp; R. D. Silverman; T. Rajala; P. Moore (Suyama test) [49]

22 27 Mar 2010 c_1,262,577 BEAE94F64C12B741 D. Domanov [18]; S. Yamada (Suyama test) [66]

12 27 Mar 2010 c_1,133 (no residue given) M. Vang; S. Batalov [60]

27 4 Apr 2010 c_40,403,531 481F26965DE16117 A. T. Höglund [66]; and in 2022, E. W. Mayer [41]

17 15 Mar 2011 c_39,395 6EF4AD31682CD751 D. Chia; T. Sorbera [1]

28 12 May 2022 c_80,807,103 790BE051D73D667E E. W. Mayer [41]; and in 2023, G. B. Gostin [69]

29 12 May 2022 c_161,614,233 AB3DBCEFFE907786 E. W. Mayer [41]; and in 2023, R. Propper

30 12 May 2022 c_323,228,467   EDFCE7FC50271D44 E. W. Mayer [41]

The only criticism here is that the modulo 2⁶⁴ residues generated by mprime before 2012 were neither from the Pépin test residue nor the outcome of the Suyama test, but from the general Fermat-PRP probabilistic primality test applied directly to the cofactor; though all of the results given are repeatable (and have been repeated), and mesh with the values that are generated by cofact or other software packages. In late 2012 Ernst W. Mayer began a long-term project to run the Pépin test on yet larger Fermat numbers, which culminated in 2022 with an announcement of a full set of results of Pépin and Suyama residues for the six Fermat numbers from F₂₅ to F₃₀. Mayer used his own mlucas software, performing the Pépin test on each Fermat number twice, using different hardware and with different length fast Fourier transforms to rule out some sources of systematic error in the FFT programming [41]. So for F₂₈, F₂₉, and F₃₀ the residue modulo 2⁶⁴ given above is derived from the final Suyama residue (A_m – B_m) mod C. The first of these three Suyama residues has been verified by Gary Gostin using mprime (to generate a PRP proof for F₂₈) and cofact (utilising the A residue saved in the proof), which confirms the result using entirely different software, in addition to different hardware [69]. A similar verification of F₂₉, using mprime instead of mlucas, is underway by another GIMPS contributor.

10. Conclusion

The Pépin tests of F₃₀ required over one billion iterations of the squaring and modulo reduction loop, and each successive Fermat number requires approximately eight times as much computation as its predecessor: a large component of the difficulty is the ever increasing size of the FFT required to carry out the modular squaring. The status of whether a Pépin test of F₃₁ is underway is unknown. The likelihood of a Pépin test being carried out in the near future for the smallest Fermat number of unknown character, F₃₃, must be regarded as even more uncertain.

For the Fermat numbers smaller than and including F₃₀, while more factors undoubtedly await discovery, they may be of sufficient size to be inaccessible to either the factoring methods or hardware we currently possess. To return to the beginning, where Christian Goldbach speculated, “it is possible for the smallest divisor of any number 2^{2^x} + 1 to be a hundred, or a hundred thousand digits, which no one will find until the end of the world”, we need look only as far as F₂₀, a number of 315,653 digits, and which might potentially, for all we know, have a smallest factor of a hundred thousand digits, with room for another couple of larger factors. The same might also possibly be true of F₂₄, a 5,050,446-digit number, which is sufficiently large to have dozens of colossal factors all greater in size than Goldbach’s conjectured, impossibly difficult-to-find smallest factor.

To look back also to Pierre de Fermat, who was almost convinced that the 2^{2^m}+1 sequence would generate arbitrarily large primes if he had been able to obtain a proof of their primality, we find he was almost right; there are (or, overwhelmingly likely to be) an infinite number of prime Fermat factors of almost any arbitrary size. But being almost right is not good enough. The problem is that these factors must be chiselled out with great difficulty from the Fermat numbers, which stonily resist any such easy discoveries chipping away at their immense size.

For any of the smaller Fermat numbers which have had a Pépin test performed, the discovery of a new factor allows the Suyama test to be readily employed to resolve the further problem of whether the factorisation is complete, by way of the new cofactor itself being prime. Most often however the cofactor will be composite and the search for further factors will remain. To this conclusion we therefore append a table of the Pépin and Suyama residues obtained for all composite Fermat numbers up to F₃₀, and a short summary of investigations on the small Fermat numbers. Separately available is also the C code of the customised version of cofact which was used to compile almost all of the verifications of results described here.

Acknowledgments

This article could not have been written without the input and generosity of Gary B. Gostin in sharing his cofact program to verify previous results, in much the same way that previous researchers had verified their predecessors’ results as part of proving their own. Gary also graciously contributed his VDF proof files for the Fermat PRP runs of F₂₇ and F₂₈, generated by mprime. A huge debt of gratitude must also go to Wilfrid Keller who provided many of the more obscure links in the chain that bind together the narrative, and whose voluminous knowledge could be relied upon for correction at many points.

Additional developments

This section will list any new results obtained after the completion of the article in August 2023.

Sadly in late September 2023 we heard of the death of Ernst W. Mayer, who had heroically undertaken the compositeness tests of the six Fermat numbers F₂₅ to F₃₀ and their cofactors; the posthumously-released version of his mlucas software (21.0.1) is currently the only software available for undertaking Pépin tests of Fermat numbers larger than F₃₀, partly thanks to addressing a number of minor bugs that prevented the previous version (20.1.1) from saving the final residue of the test. Version 21.0.1 also includes Ernst’s implementation of the Suyama test.

On 1 November 2023 a pseudonymous GIMPS contributor completed a Pépin test of F₂₉, verifying Ernst’s work with completely different hardware and software, and has kindly shared the proof file generated by mprime. The Suyama test carried out by cofact fully verifies Ernst’s results listed in the following section.

The zip file of my customised version of cofact has been slightly updated several times (up until March 2024) but has now been publicly released on GitHub, at https://github.com/primesearch/cofact including two branches for Gary Gostin’s latest release, and my customised version.

Some small touches to the formatting (such as indicating extra information by dotted underlining), and some bolding or aligning of monospaced output from cofact, have been added since the original publishing of August 2023, as well as some very minor corrections.

Appendix 1. Pépin and Suyama residues, F₁ – F₃₀

Using cofact, Catherine Cowie ran the Pépin test on all Fermat numbers up to F₂₅, and Suyama tests up to F₂₇ as verification, so the remainder of the table was supplemented by the results of:

F₂₆: Pépin test by Gary Gostin using cofact, as the author’s mprime run did not yield a full set of S–H residues;
F₂₇ – F₃₀: Pépin and Suyama tests by Ernst Mayer using mlucas; again, the author’s mprime run only yielded the main Pépin residue modulo 2⁶⁴ and not the other S–H values. Two sets of the Suyama results are verifiable with Gostin’s contributed proofs of F₂₇ and F₂₈.

The quantities P_m, A_m, B_m, and S_m are all tacitly reduced modulo F_m, prior to further modular reduction.

m P_m mod 2⁶⁴ (hex) P_m mod 2³⁶ P_m mod 2³⁶–1 P_m mod 2³⁵–1 A_m mod 2⁶⁴ (hex) A_m mod 2³⁶ A_m mod 2³⁶–1 A_m mod 2³⁵–1 B_m mod 2⁶⁴ (hex) B_m mod 2³⁶ B_m mod 2³⁶–1 B_m mod 2³⁵–1 S_m mod 2⁶⁴ (hex) S_m mod 2³⁶ S_m mod 2³⁶–1 S_m mod 2³⁵–1 gcd
(A_m – B_m,
C)

0 Neither the Pépin test nor the Suyama test may be applied to the zeroth Fermat number

1–4 –1 –1 –1 –1 1 1 1 1 These Fermat numbers are prime, so the Suyama test is not required

5 9D894F 10324303 10324303 10324303 B48B4570 3029026160 3029026160 3029026160 } Fermat numbers F₅ to F₁₁ are completely factored,
so the Suyama test is not required

6 A497F7120F395E35 8845352501 9017941414 9190530327 79763C94C301A5F2 20451534322 20578896315 20706258308

7 95984E80E902C504 3909272836 44591026080 5799525263 7C36D29F9594A24B 66934055499 8117436329 34344873225

8 6507E50AC84D66B3 46310188723 35403253324 30627284506 BD369DB0333BDAB9 859560633 49398862793 7169939333

9 B8E74A7493EECD76 19661770102 54966870189 28173182079 C92C3A1A3EFD953C 44006479164 9621194327 19262051920

10 E035DD28798E8098 36399120536 54182679152 28022031617 D8FD758BF8EF405D 51421069405 27332107831 16611700203

11 38AD5BCF85A1DD28 66666487080 44928212591 3934743084 2F2F83E6A14C7C3A 28475948090 45109638561 22705527920

12 06C3171F0746A313 64546579219 3387502849 5300454051 8346D942AF82520A 11534488074 48121973657 11150519550 98D29BB505C82D27 21571841319 31828999134 249760013 06D3316513FC3333 21810131763 65765080811 7388471481 1

13 D79356EC3B040B5E 52529728350 52864871946 3434508623 4B3EA30710A4989A 30343993498 52451231872 9804790336 4F2A986CE8427164 55436276068 19383040962 1680477711 E77153C999263C25 41224125477 2496190587 25908858272 1

14 CC52BC3C94F9774A 54038984522 1986493987 15173315214 E110B2DF4898DFD7 65642487767 21972275522 32620083537 96D8E2B802C733B3 34406347699 24532874398 27969365260 FC6DCDF563F934D2 23152112850 20505684606 16876703551 1

15 D534BCF1A89FCA9F 7124011679 42435904961 14110954287 46C3D48B9041D9E3 49664874979 4867942482 25174316024 7F08E8A9EEFDD710 42664318736 28937048602 22628990761 167C0419066997DF 38762289119 67988866249 9771151649 1

16 40ABB0C5BFF05CB5 24695037109 65390296136 173595305 7A3617ECEEB13091 55544197265 25060016989 20710633406 DFBA3FBD0A4A225A 56007205466 26702937368 29834196943 02664CA2851BBDCA 10823122378 38394099743 763967994 1

17 5AFC1FE36DC81DDD 14726733277 2770550506 14982977589 907B654AA857D7A8 45774002088 22659343630 9924649749 BEDA5B4F3DC4EADD 65460824797 63727741388 5932131125 8EF31C72B0209FF0 11544862704 30808052802 15101673067 1

18 506A5A0ABC27E6F0 46106404592 14070013587 10874364700 BCBFB1C446912EAD 18363788973 16198816711 5160281264 689AC15EAF3057EE 63068723182 29076663800 15794027617 CC9626F5A95549B1 24315775409 41329922521 4867623401 1

19 8C9339452E75F19C 22254317980 58676148574 6407009455 449FBCA640B4FA27 26855406119 30933529616 405458041 4E81A5FE01B9AC83 60158487683 52398778242 18465526654 14103D7C8A6FDF38 53862195000 27723811980 23470815198 1

20 78791573ED3DE5F1 16865158641 35626292569 15265819636 11BEF945BB1F0767 24614209383 29963929564 26085093865 This Fermat number has no known factors, so the Suyama test cannot proceed

21 C4AE66D539B41B40 22442941248 300257643 30981963597 A07023647D42B4D5 19281392853 11280367853 12351604643 DA11FF47C9F2DBA7 33452907431 25506585220 5803823552 1A6B2145AEB90471 24406197361 18942332167 15719707512 1

22 77F6FA403A09D72A 973723434 8733349067 12323430823 1B7A892DC7F0EC35 59189029941 62994050515 21359120063 F2F13497115814AD 30355756205 58598662170 31225537268 8F2B6FC5AA6AF96A 24333973866 30570899199 5450609407 1

23 50E1F11B55196BBB 48672369595 60596902712 4259642653 14E2143DD7E57ABB 59456715451 10275710011 27248444876 1029BE52A5446CDA 11362659546 54792073816 3050368568 5574287CB97265BA 54650889658 13707222996 8874908179 1

24 17311B7E131E106C 60450279532 68627742455 32898231088 6EC4A4806BE07FAA 1809874858 49220810423 7419597027 This Fermat number has no known factors, so the Suyama test cannot proceed

25 CB913B6E3B1FFE2A 61121494570 15369168494 9073733940 7B6B087B84A45562 49470002530 66886679148 26994100025 2909830729BFA110 30765195536 21153567739 30348546187 7A551893ACF4BE4E 15786622542 65496009072 34178045549 1

26 2B58BDE2A0C14045 11286954053 2307231107 9689287987 FBB406B3A281838C 15611298700 7371940776 2193939191 25F5AB0FFC728C87 68659874951 20444894301 32173443562 B7BD14979ACF222E 32662037038 15466936163 6416457631 1

27 043A6C8B9272B297 49701630615 39732934618 30710305624 C3B191C45CCD7820 18736838688 55240256170 21887650168 485F292142F953EC 5418603500 26481669619 20036545122 79E89190C56372B7 3311628983 29330680430 2608954171 1

28 468731C3E6F13E8F 16759471759 9104636564 30476727665 7CAE1275B362B2CA 24484426442 30894284803 20461105324 BD496177DB5155A0 33744311712 3778945069 33633822046 790BE051D73D667E 7906092670 55362539930 4159568998 1

29 BECE1E5FFBE5EC12 68650658834 21246329964 17796269382 9BD416DB3918C152 48202563922 58920206666 32748692453 30AFC6010F62884B 4553082955 6544795868 7473784009 AB3DBCEFFE907786 68695390086 41564307636 13349243207 1

30 A70C2A3DB98D6D9D 58947628445 59810773698 26425548225 1D7AA56A5428333C 44361593660 40327643421 30698378043 6F856680482D3F4E 1210924878 48656226334 9072042323 EDFCE7FC50271D44 52884348228 34401987830 9723857098 1

Appendix 2. Summary of events

As the chronology of the investigation of the small Fermat numbers is something of a patchwork, we here summarise the order of discoveries for each Fermat number in relative isolation from one another. A complete breakdown of values of factors is given elsewhere. The letters p_i, c_i, and u_i here indicate a prime number, or a composite number, or a number of unknown character, that is i digits in decimal form. An asterisk (*) indicates a number was asserted to be prime or passed a probable prime test, and the mark (′) differentiates factors of approximately the same magnitude. Discoverers or provers are cited by numbered references.

F_m Factorisation Character, known factors Year Discoverer(s) / Prover(s) Event

F₀
F₁
F₂
F₃
F₄ = p₁ }
= p₁ }
= p₂ }
= p₃ }
= p₅ } prime 1640 Fermat [22, op. cit.] All Fermat numbers F_m asserted to be prime

These are the only known Fermat primes.
At some point in the two decades after 1640, Fermat claimed to have a proof of primality for all Fermat numbers using his method of infinite descent, only to subsequently discover that his proof was faulty. He appears to have nevertheless believed his conjecture to be true, and highly desired that someone would improve the proof to clinch the result; for instance in 1654 he wrote to Pascal attempting to interest him in the problem, and as late as 1658 he is writing to an English correspondent, Kenelm Digby.

F₅ = p*₁₀ prime* 1640 Fermat [22] Claimed to be prime

= p₃ · u₇ 2 factors, 1 definitely prime 1732 Euler [20] Discovery of p₃ factor

= p₃ · p₇ semiprime, completely factored ? Euler Primality of p₇ cofactor shown

Euler discovered the first Fermat factor by [O.S.] 26 September 1732, the date of his lecture to the Saint Petersburg Academy. What is not clear is how quickly he came to discover that the 7-digit cofactor was also prime (a task some 25 times smaller than the potential worst case trial division of F₅). The previous largest known prime was Ibn Fallûs / Pietro Cataldi’s M₁₉ = 524,287, so the cofactor would have been the new largest known prime until Euler’s own proof of the primality of M₃₁.

F₆ = p*₂₀ prime* 1640 Fermat [22] Claimed to be prime

= u₂₀ unknown 1732 Euler [20] Factorisation of F₅ disproved Fermat’s conjecture

= p₆ · p*₁₄ semiprime* 1855 Clausen [2] Complete factorisation claimed

= c₂₀ composite 1877 Lucas [38] Compositeness test (Pell subsequence), Lucas being unaware of Clausen’s factorisation

= p₆ · u₁₄ 2 factors, 1 definitely prime 1880 Landry [34] Rediscovery of first p₆ factor

= p₆ · p₁₄ semiprime, completely factored 1880 Landry, Le Lasseur [40] Primality of p₁₄ cofactor shown

Clausen’s 1 January 1855 letter to Gauss claimed both factors to be prime, without proof. He wrote, »Auch habe ich gefunden, daß die Zahl 2⁶⁴+1 in die beiden Primfactoren 274177 und 67280421310721 zerlegt werden kann; die letzere ist, so viel ich weiß, die größte bis jetzt bekannte Primzahl.« (“Also I have found that the number 2⁶⁴+1 can be broken into two prime factors 274177 and 67280421310721; the latter is, so far as I know, the largest known prime number.”)
For F₇ and following, we will omit the first two chronological events, that in 1640 Fermat believed all Fermat numbers to be prime, whereas Euler disproved the conjecture in 1732 by finding the first Fermat divisor.

F₇ = c₃₉ composite 1905 Morehead [43]; Western [64]; 1952, Robinson [52] Pépin tests showed F₇ to be composite

= p₁₇ · p₂₂ semiprime, completely factored 1970 Morrison & Brillhart [45,46] Fermat number decomposed into two prime factors

Strictly speaking Morrison and Brillhart’s factorisation broke F₇ into two numbers of unknown character, which were both found to be prime. Compare F₉ below.

F₈ = c₇₈ composite 1909 Morehead & Western [44]; 1952, Robinson [52] Pépin test showed F₈ to be composite

= p₁₆ · p*₆₂ 2 factors, 1 definitely prime 1980 Brent & Pollard [9] Discovery of first prime factor

= p₁₆ · p₆₂ semiprime, completely factored 1980 Williams [9] Proof of p₆₂ cofactor’s primality

Brent and Pollard strongly suspected p*₆₂ to be prime after it passed about 100 Rabin tests.

F₉ = p₇ · u₁₄₈ 1 prime factor 1903 Western [17] Discovery of first prime factor

= p₇ · c₁₄₈ 1 prime factor, composite cofactor 1967 Brillhart [28] Cofactor shown to be composite

= p₇ · p*₄₉ · p*₉₉ 3 factors, 1 definitely prime 1990 Lenstra, Lenstra, Manasse, & Pollard [36] Cofactor split into 2 probably prime factors

= p₇ · p₄₉ · p₉₉ 3 prime factors, completely factored 1990 Odłyżko [36] New factors proven to be prime

F₁₀ = c₃₀₉ composite 1952 Robinson [52]; 1953, Lehmer [52]; 1960, Paxson [47] Pépin tests showed F₁₀ to be composite

= p₈ · u₃₀₁ 1 prime factor 1953 Selfridge [52,54] Discovery of first prime factor

= p₈ · p₁₀ · u₂₉₁ 2 prime factors 1962 Brillhart [11] Discovery of second prime factor

= p₈ · p₁₀ · c₂₉₁ 2 prime factors, composite cofactor 1967 Brillhart [28] Cofactor shown to be composite

= p₈ · p₁₀ · p₄₀ · p₂₅₂ 4 prime factors, completely factored 1995 Brent [6,7] Discovery of third factor, primality proof of p₂₅₂ cofactor

F₁₁ = p₆ · p′₆ · u₆₀₆ 2 prime factors 1899 Cunningham [17] Discovery of two prime factors

= p₆ · p′₆ · c₆₀₆ 2 prime factors, composite cofactor 1970s Wagstaff [25] Cofactor shown to be composite

= p₆ · p′₆ · p₂₂ · c₅₈₄ 3 prime factors, composite cofactor 1988 Brent [5,6] Discovery of third factor, cofactor composite

= p₆ · p′₆ · p₂₂ · p₂₁ · p*₅₆₄ 5 factors, 4 definitely prime 1988 Brent [5,6] Discovery of fourth factor, cofactor probably prime

= p₆ · p′₆ · p₂₂ · p₂₁ · p₅₆₄ 5 prime factors, completely factored 1988 Morain [5,6] Proof of p₅₆₄ cofactor’s primality

This is the largest Fermat number to be completely factored, but was not the most recent, due to the size of the second-largest factor p₂₂ making it much easier to discover than p₄₀ | F₁₀ or p₄₉ | F₉.

F₁₂ = p₆ · u_1,228 1 prime factor 1877 Pervushin [3]; 1878, Lucas [4,39] Discovery of first prime factor

= p₆ · p₈ · p′₈ · u_1,213 3 prime factors 1903 Western [17] Discovery of two prime factors

= p₆ · p₈ · p′₈ · p₁₂ · u_1,202 4 prime factors 1974 Hallyburton & Brillhart [28] Discovery of fourth prime factor

= p₆ · p₈ · p′₈ · p₁₂ · c_1,202 4 prime factors, composite cofactor 1970s Wagstaff [25] Cofactor shown to be composite

= p₆ · p₈ · p′₈ · p₁₂ · p₁₆ · c_1,187 5 prime factors, composite cofactor 1986 Baillie [61] Discovery of fifth factor, cofactor composite

= p₆ · p₈ · p′₈ · p₁₂ · p₁₆ · p₅₄ · c_1,133 6 prime factors, composite cofactor 2010 Vang [60] (cofactor: also Batalov, Schindel) Discovery of sixth factor, cofactor composite

The version of the GMP-ECM program by Paul Zimmerman and customised by Alex Kruppa, which Mike Vang used to find the sixth known prime factor, ran a compositeness test on the cofactor immediately after discovering the factor. Compositeness was verified by Serge Batalov and others.

F₁₃ = c_2,467 composite 1960 Paxson [47]; 1961, Hurwitz & Selfridge [55] Pépin tests showed F₁₃ to be composite

= p₁₃ · u_2,454 1 prime factor 1974 Hallyburton & Brillhart [28] Discovery of first prime factor

= p₁₃ · c_2,454 1 prime factor, composite cofactor 1970s Wagstaff [25] Cofactor shown to be composite

= p₁₃ · p₁₉ · u_2,436 2 prime factors 1991 Crandall [14] Discovery of second prime factor

= p₁₃ · p₁₉ · c_2,436 2 prime factors, composite cofactor 1991 Lenstra; Keller [30] Cofactor shown to be composite

= p₁₃ · p₁₉ · p′₁₉ · c_2,417 3 prime factors, composite cofactor 1991 Crandall [14] Discovery of third factor, cofactor composite

= p₁₃ · p₁₉ · p′₁₉ · p₂₇ · c_2,391 4 prime factors, composite cofactor 1995 Brent [6,8] Discovery of fourth factor, cofactor composite

F₁₄ = c_4,933 composite 1961 Hurwitz & Selfridge [29,55]; 1987, Young & Buell [68] Pépin test showed F₁₄ to be composite

= p₅₄ · c_4,880 1 prime factor, composite cofactor 2010 Rajala [49] (cofactor: also Lipp; Silverman; Moore) Discovery of first factor, cofactor composite

F₁₅ = p₁₀ · u_9,856 1 prime factor 1925 Kraïtchik [33] Discovery of first prime factor

= p₁₀ · c_9,856 1 prime factor, composite cofactor 1984 Suyama [56] Cofactor shown to be composite

= p₁₀ · p₁₆ · u_9,840 2 prime factors 1987 Gostin [26] Discovery of second prime factor

= p₁₀ · p₁₆ · c_9,840 2 prime factors, composite cofactor 1987 Suyama [57]; Baillie [61] New cofactor; still composite

= p₁₀ · p₁₆ · p₃₃ · u_9,808 3 prime factors 1997 Crandall & van Halewyn [8] Discovery of third prime factor

= p₁₀ · p₁₆ · p₃₃ · c_9,808 3 prime factors, composite cofactor 1997 Crandall & Brent [8] New cofactor also composite

F₁₆ = p₉ · u_19,720 1 prime factor 1953 Selfridge [52,54] Discovery of first prime factor

= p₉ · c_19,720 1 prime factor, composite cofactor 1987 Baillie [61] Cofactor shown to be composite

= p₉ · p₂₇ · u_19,694 2 prime factors 1996 Crandall & Dilcher [8] Discovery of second prime factor

= p₉ · p₂₇ · c_19,694 2 prime factors, composite cofactor 1996 Brent & Crandall [8] New cofactor also composite

F₁₇ = p₁₄ · u_39,444 1 prime factor 1978 Gostin [25] Discovery of first prime factor

= p₁₄ · c_39,444 1 prime factor, composite cofactor 1987 Baillie [32] Cofactor shown to be composite

= p₁₄ · p₄₉ · u_39,395 2 prime factors 2011 Bessell [1] Discovery of second prime factor

= p₁₄ · p₄₉ · c_39,395 2 prime factors, composite cofactor 2011 Chia; Sorbera [1] New cofactor also composite

F₁₈ = p₈ · u_78,907 1 prime factor 1903 Western [17] Discovery of first prime factor

= p₈ · c_78,907 1 prime factor, composite cofactor 1990 Chudnovsky twins [62] Cofactor shown to be composite

= p₈ · p₂₃ · u_78,884 2 prime factors 1996 Crandall, McIntosh, & Tardif [8] Discovery of second prime factor

= p₈ · p₂₃ · c_78,884 2 prime factors, composite cofactor 1999 Crandall [32] New cofactor also composite

F₁₉ = p₁₁ · u_157,816 1 prime factor 1962 Riesel [51] Discovery of first prime factor

= p₁₁ · p₁₂ · u_157,804 2 prime factors 1963 Wrathall [67] Discovery of second prime factor

= p₁₁ · p₁₂ · c_157,804 2 prime factors, composite cofactor 1993 Crandall, Doenias, Norrie, & Young [15] Cofactor shown to be composite

= p₁₁ · p₁₂ · p₃₅ · u_157,770 3 prime factors 2009 Bessell [66] Discovery of third prime factor

= p₁₁ · p₁₂ · p₃₅ · c_157,770 3 prime factors, composite cofactor 2009 King; Kruppa; Childers [66] New cofactor also composite

F₂₀ = c_315,653 composite 1987 Young & Buell [68]; 1993, Crandall, Doenias, Norrie, & Young [15] Pépin tests showed F₂₀ to be composite

F₂₁ = p₁₃ · u_631,294 1 prime factor 1963 Wrathall [67] Discovery of first prime factor

= p₁₃ · c_631,294 1 prime factor, composite cofactor 1993 Crandall, Doenias, Norrie, & Young [15] Cofactor shown to be composite

F₂₂ = c_1,262,612 composite 1993 Crandall, Doenias, Norrie, & Young [15]; Trevisan & Carvalho [58]; 1999, Crandall et al. [16] Pépin tests showed F₂₂ to be composite

= p₃₅ · u_1,262,577 1 prime factor 2010 Bessell [18] Discovery of first prime factor

= p₃₅ · c_1,262,577 1 prime factor, composite cofactor 2010 Domanov [18]; Yamada [66] Cofactor shown to be composite

F₂₃ = p₉ · u_2,525,215 1 prime factor 1878 Pervushin [4] Discovery of first prime factor

= p₉ · c_2,525,215 1 prime factor, composite cofactor 2000 Crandall, Mayer, & Papadopoulos [16] Cofactor shown to be composite

F₂₄ = c_5,050,446 composite 1999 Crandall, Mayer, & Papadopoulos [16] Pépin tests showed F₂₄ to be composite

F₂₅ = p₁₄ · u_10,100,878 1 prime factor 1963 Wrathall [67] Discovery of first prime factor

= p₁₄ · p₁₈ · u_10,100,860 2 prime factors 1985 Gostin [26] Discovery of second prime factor

= p₁₄ · p₁₈ · p₁₉ · u_10,100,842 3 prime factors 1987 McLaughlin [12] Discovery of third prime factor

= p₁₄ · p₁₈ · p₁₉ · c_10,100,842 3 prime factors, composite cofactor 2009 Yamada [66]; Höglund [66] Cofactor shown to be composite

F₂₆ = p₁₄ · u_20,201,768 1 prime factor 1963 Wrathall [67] Discovery of first prime factor

= p₁₄ · c_20,201,768 1 prime factor, composite cofactor 2009 Höglund [66]; 2022, Mayer [41] Cofactor shown to be composite

F₂₇ = p₁₅ · u_40,403,548 1 prime factor 1963 Wrathall [67] Discovery of first prime factor

= p₁₅ · p₁₈ · u_40,403,531 2 prime factors 1985 Gostin [26] Discovery of second prime factor

= p₁₅ · p₁₈ · c_40,403,531 2 prime factors, composite cofactor 2010 Höglund [66]; 2022, Mayer [41] Cofactor shown to be composite

F₂₈ = p₂₂ · u_80,807,103 1 prime factor 1997 Taura [16] Discovery of first prime factor

= p₂₂ · c_80,807,103 1 prime factor, composite cofactor 2022 Mayer [41]; 2023, Gostin [69] Cofactor shown to be composite

F₂₉ = p₁₆ · u_161,614,233 1 prime factor 1980 Gostin & McLaughlin [27] Discovery of first prime factor

= p₁₆ · c_161,614,233 1 prime factor, composite cofactor 2022 Mayer [41] Cofactor shown to be composite

F₃₀ = p₁₅ · p₁₆ · u_323,228,467 2 prime factors 1963 Wrathall [67] Discovery of first two prime factors

= p₁₅ · p₁₆ · c_323,228,467 2 prime factors, composite cofactor 2022 Mayer [41] Cofactor shown to be composite

Appendix 3. Other materials

The revised version 0.9.1 of cofact is now available at GitHub: https://github.com/primesearch/cofact/tree/cxc (December 2024)

The C code can be inspected at: https://64ordle.au/fermat/cofact.txt

A zip file containing a Mac OS X Intel binary of the older version 0.73c, the C code, makefile, shell scripts, and other logs, is still downloadable from: https://64ordle.au/fermat/cofact.zip (7.7 MB, MD5 ef8e8431682000173f211b393db21e49)

This zip file also includes a verifiable delay function (VDF) proof of F₁₇ for testing cofact’s handling of proof files, and a Mac OS X Intel binary of pellucid, for examining Lucas’s sequence (see section 3 above). Besides showing that the only known factor of F₂₃ is also a factor of a companion Pell number V_2²³ (2, –1), pellucid also was used to discover a large number of additional factors of other companion Pell numbers not previously known, including four other Fermat divisors.

While cofact can perform the Pépin test for Fermat numbers up to F₃₀ it is computationally expensive beyond F₂₄; thus VDF proof files for these Fermat numbers are useful for running the Suyama test without the expensive first step of the test. Proofs for F₁₂ up to F₂₉ may be downloaded from https://64ordle.au/fermat/F12.proof for F₁₂, the proof for F₁₃ from https://64ordle.au/fermat/F13.proof, and so on up to F₂₉ (November 2024). The MD5 checksums and download sizes for these proofs are listed at: https://64ordle.au/fermat/

As mentioned in the course of the essay above, compilation of cofact for other platforms requires both GMP and gwnum; GMP should be installed at the system level, and the cofact cmake.sh script will create symbolic links pointing to required Prime95/gwnum files in some other specified directory. GMP is available from https://gmplib.org/#DOWNLOAD, and Prime95/gwnum as source code at https://mersenne.org/download.

References

1. D. Bessell, New factor for F₁₇, mersenneforum.org thread 10835, post 1 (2011); cofactor compositeness tests appear in replies at post 6 (D. Chia) and post 9 (T. Sorbera)
2. K.-R. Biermann, Thomas Clausen, Mathematiker und Astronom, J. für die reine und angewandte Mathematik 216 (1964), 159–198 (see page 185, relating a letter by Clausen to C. F. Gauss, dated 1 January 1855). DOI 10.1515/crll.1964.216.159
3. V. Y. Bouniakowsky, Nouveau cas de divisibilité des nombres de la forme 2^{2^m}+1, trouvé par le révérend père J. Pervouchine, Bulletins de l’Académie des sciences de Saint-Pétersbourg 24 (1878), 559
4. V. Y. Bouniakowsky, Encore un nouveau cas de divisibilité des nombres de la forme 2^{2^m}+1, Bulletins de l’Académie des sciences de Saint-Pétersbourg 25 (1879), 63–64
5. R. P. Brent, Factorization of the eleventh Fermat number (preliminary report), Amer. Math. Soc. Abstracts 10 (1989), 89T-11-73
6. R. P. Brent, Factorization of the tenth and eleventh Fermat numbers, Report TR-CS-96-02, Computer Sciences Laboratory, Australian National Univ., Canberra, Feb. 1996, 25 pp.
7. R. P. Brent, Factorization of the tenth Fermat number, Math. Comp. 68 (1999), 429–451. MR 1489968, DOI 10.1090/S0025-5718-99-00992-8
8. R. P. Brent, R. E. Crandall, K. Dilcher, C. van Halewyn, Three new factors of Fermat numbers, Math. Comp. 69 (2000), 1297–1304. MR 1697645, DOI 10.1090/S0025-5718-00-01207-2
9. R. P. Brent, J. M. Pollard, Factorization of the eighth Fermat number, Math. Comp. 36 (1981), 627–630. MR 606520, DOI 10.1090/S0025-5718-1981-0606520-5
10. S. Brentjes, The first [seven] perfect numbers and three types of amicable numbers in a manuscript on elementary number theory by Ibn Fallûs, Erdem 5(11) (1988), 467–483
11. J. Brillhart, Some miscellaneous factorizations, Math. Comp. 17 (1963), 447–450. DOI 10.1090/S0025-5718-63-99176-2
12. J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, S. S. Wagstaff, Jr, Factorizations of bⁿ±1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers, Contemporary Math. vol. 22, third edition, Amer. Math. Soc., Providence, Rhode Island (2002). MR 996414, DOI 10.1090/conm/022
13. P. A. Cataldi, Trattato de’ numeri perfetti, Heredi di Giovanni Rossi, Bologna, 1603
14. R. E. Crandall, Projects in scientific computation, TELOS. The Electronic Library of Science, Santa Clara, Califonia; Springer-Verlag, New York, 1994. MR 1258083, DOI 10.1007/978-1-4612-4324-3
15. R. E. Crandall, J. Doenias, C. Norrie, J. Young, The twenty-second Fermat number is composite, Math. Comp. 64 (1995), 863–868. MR 1277765, DOI 10.1090/S0025-5718-1995-1277765-9
16. R. E. Crandall, E. W. Mayer, J. S. Papadopoulos, The twenty-fourth Fermat number is composite, Math. Comp. 72 (2003), 1555–1572. MR 1972753, DOI 10.1090/S0025-5718-02-01479-5
17. A. J. C. Cunningham, A. E. Western, On Fermat’s numbers, Proc. Lond. Math. Soc. (2) 1 (1904), 175. DOI 10.1112/plms/s2-1.1.175
18. D. Domanov, F₂₂ factored, mersenneforum.org thread 9605; announcement, post 1; cofactor compositeness test, post 12 (2010)
19. Euclid, Elements, Book IX, 36
20. L. Euler, Observationes de theoremate quodam Fermatiano, aliisque ad numeros primos spectantibus, Commentarii academiae scientiarum Petropolitanae 6 (1738), 103–107; translated from Latin by D. Zhao (2006), J. Bell (2008)
21. L. Euler, other writings in Leonhardi Euleri Opera omnia:

Eneström 54, proof of Fermat’s little theorem (1736)
Eneström 798, Euclid–Euler theorem (1747)
Eneström 262, Euler’s totient theorem (1755)
Eneström 461, primality of M₃₁ = 2³¹ – 1 (letter OO 233 to Johann Bernoulli III, ca. 1771/2)

22. P. de Fermat, Œuvres de Fermat, volume 2: Correspondence, Gauthier-Villars et fils, Paris (1894), XLIII. 205–206 (second letter to Frénicle), XLIV. 206–212 (third letter, 18 October 1640)
23. C. R. Fletcher, A reconstruction of the Frenicle–Fermat correspondence of 1640, Historia Mathematica 18 (1991), 344–351
24. C. Goldbach, in Leonhardi Euleri Opera Omnia, Series IVA/4, Correspondence with Christian Goldbach, Springer Basel (2015). Letter 8: Part I, pp. 118–119 (Latin), Part II, pp. 612–613 (English)
25. G. B. Gostin, A factor of F₁₇, Math. Comp. 35 (1980), 975–976. MR 572869, DOI 10.1090/S0025-5718-1980-0572869-7
26. G. B. Gostin, New factors of Fermat numbers, Math. Comp. 64 (1995), 393–395. MR 1265015, DOI 10.1090/S0025-5718-1995-1265015-9
27. G. B. Gostin, P. B. McLaughlin, Jr, Six new factors of Fermat numbers, Math. Comp. 38 (1982), 645–649. MR 645680, DOI 10.1090/S0025-5718-1982-0645680-8
28. J. C. Hallyburton, Jr, J. Brillhart, Two new factors of Fermat numbers, Math. Comp. 29 (1975), 109–112. MR 369225, DOI 10.1090/S0025-5718-1975-0369225-1. Corrigenda ibid. 30 (1976), 198.
29. A. Hurwitz, J. L. Selfridge, Fermat numbers and perfect numbers, Notices Amer. Math. Soc. 8 (1961), 601, abstract 587-104.
30. W. Keller, email correspondence from and to Arjen K. Lenstra (1991)
31. W. Keller, Factors of Fermat numbers and large primes of the form k·2ⁿ + 1, II, Uni. of Hamburg preprint (1992), 1–40 + 16 un-numbered pp.
32. W. Keller, Prime factors k.2ⁿ + 1 of Fermat numbers F_m and complete factoring status, archived version of prothsearch.net/fermat.html (2001)
33. M. B. Kraïtchik, On the factorization of 2ⁿ ± 1, Scripta Math. 18 (1952), 39–52. MR 14,121e
34. F. Landry, Sur la décomposition du nombre 2⁶⁴ + 1, Comptes rendus hebdomadaires des séances de l’Académie des sciences de Paris 91 (1880), 138 (see also [65])
35. D. H. Lehmer, Recent discoveries of large primes, Math. Tables Aids Comput. 6 (1952), 61. MR 234612, DOI 10.1090/S0025-5718-52-99405-2
36. A. K. Lenstra, H. W. Lenstra, Jr, M. S. Manasse, J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 61 (1993), 319–349. MR 1182953, DOI 10.1090/S0025-5718-1993-1182953-4, Addendum ibid. 64 (1995), 1357.
37. F. É. A. Lucas, in Comptes rendus hebdomadaires des séances de l’Académie des sciences de Paris

Note sur l’application des séries récurrentes à la recherche de la loi de distribution des nombres premiers, 82 (10 January 1876), 165–167
Sur la division de la circonférence en parties égales, 85 (16 July 1877), 136–139

38. F. É. A. Lucas, Considérations nouvelles sur la théorie des nombres premiers et sur la division géométrique de la circonférence en parties égales, Association française pour l’avancement des sciences, Comptes-rendus de la 6^e session, Le Havre (1877), 159–167
39. F. É. A. Lucas, Théorèmes d’arithmétique, Atti reale Accademia delle scienze di Torino 13 (1877–78), 271–284
40. F. É. A. Lucas, Récréations mathématiques, 2^nd edition, volume 2, Gauthier-Villars et fils, Paris (1896), 230–235
41. E. W. Mayer, Pépin tests of Fermat numbers beyond F₂₄, mersenneforum.org thread 13610 (2013–22), various posts:

Pépin S–H residues for F₂₇ and F₂₈, posts 2 and 4 (2013)
Pépin S–H residues for F₂₉, post 52 (2017)
Pépin S–H residues for F₃₀, post 84, “F30 primality test and matching double-check” (2022)
Suyama tests for F₂₅ to F₃₀, post 83, “F25–F30 cofactor status, Part 2” (2022)

42. M. Mersenne, Cogitata physico mathematica, in quibus tam naturæ quàm artis effectus admirandi certissimis demostrationibus explicantur, Antoine Berthier, Paris, 1644
43. J. C. Morehead, Note on Fermat’s numbers, Bull. Amer. Math. Soc. 11 (1905), 543–545. MR 1558255, DOI 10.1090/S0002-9904-1905-01255-6
44. J. C. Morehead, A. E. Western, Note on Fermat’s numbers, Bull. Amer. Math. Soc. 16 (1909), 1–6. MR 1558828, DOI 10.1090/S0002-9904-1909-01841-5
45. M. A. Morrison, J. Brillhart, The factorization of F₇, Bull. Amer. Math. Soc. 77 (1971), 264. MR 268113, DOI 10.1090/S0002-9904-1971-12711-8
46. M. A. Morrison, J. Brillhart, A method of factoring and the factorization of F₇, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5
47. G. A. Paxson, The compositeness of the thirteenth Fermat number, Math. Comp. 15 (1961), 420. MR 124264, DOI 10.1090/S0025-5718-1961-0124264-0
48. T. Pépin, Sur la formule 2^2ⁿ + 1, Comptes rendus hebdomadaires des séances de l’Académie des sciences de Paris 85 (1877), 329–331
49. T. Rajala, GIMPS’ second Fermat factor, mersenneforum.org thread 9485, post 1; posts 13, 18, and 19 (2010); cofactor compositeness tests, post 5 (W. B. Lipp); post 12 (R. D. Silverman); post 24 (P. Moore)
50. R. Rashed, Ibn al-Hatham et les nombres parfaits, Historia Mathematica 16 (1989), 343–352
51. H. I. Riesel, A factor of the Fermat number F₁₉, Math. Comp. 17 (1963), 458. DOI 10.1090/S0025-5718-63-99175-0
52. R. M. Robinson, Mersenne and Fermat numbers, Proc. Amer. Math. Soc. 5 (1954), 842–846. MR 64787, DOI 10.1090/S0002-9939-1954-0064787-4
53. R. M. Robinson, A report on primes of the form k·2ⁿ+1 and on factors of Fermat numbers, Proc. Amer. Math. Soc. 9 (1958), 673–681. MR 96614, DOI 10.1090/S0002-9939-1958-0096614-7, Erratum ibid., 9 (1958), 1000
54. J. L. Selfridge, Factors of Fermat numbers, Math. Tables Aids Comput. 7 (1953), 274–275. DOI 10.1090/S0025-5718-53-99350-8
55. J. L. Selfridge, A. Hurwitz, Fermat numbers and Mersenne numbers, Math. Comp. 18 (1964), 146–148. MR 159775, DOI 10.1090/S0025-5718-1964-0159775-8
56. H. Suyama, The cofactor of F₁₅ is composite, Abstracts Amer. Math. Soc. 5 (1984), 271–272
57. H. Suyama, The new cofactor of F₁₅ is still composite, written communication (23 October 1987)
58. V. Trevisan, J. B. Carvalho, The composite character of the twenty-second Fermat number, J. Supercomputing 9 (1995), 179–182. DOI 10.1007/BF01245403
59. E. Ulivi, Benedetto da Firenze nella tradizione abacistica, Bollettino di storia delle scienze matematiche 22: Benedetto di Firenze (1429–1479): un maestro d’abaco del XV secolo (2002), 10–13
60. M. Vang, F₁₂ has a factor, mersenneforum.org thread 9610, post 1 and post 9 (2010); compositeness tests, post 2 (S. Batalov) and post 4 (A. Schindel)
61. S. S. Wagstaff, Jr, Update #5 to Factorizations of bⁿ ± 1 (1987), 6 pp. (this is a supplement to the first edition of [12])
62. S. S. Wagstaff, Jr, Cover letter for Page 61 (1 October 1990)
63. K. Weber, An experiment in high-precision arithmetic on shared memory microprocessors, SIGSAM Bulletin, 24(2) (1990), 22–40
64. A. E. Western, Note on Fermat’s numbers and the converse of Fermat’s theorem, Proc. Lond. Math. Soc (2) 3 (1905), xxi–xxii. DOI 10.1112/plms/s2-3.1.1-v
65. H. C. Williams, How was F₆ factored? Math. Comp. 61 (1993), 463–474. MR 1182248, DOI 10.1090/S0025-5718-1993-1182248-9
66. G. F. Woltman, GIMPS’ first Fermat factor, mersenneforum.org thread 8842, post 1 (2009), announcement of new factor of F₁₉; with replies by:

J. R. King, compositeness test of c_157,770 | F₁₉ cofactor, post 5 (2009)
A. Kruppa, compositeness test of F₁₉ cofactor, post 6 (2009)
‘E. P.’, compositeness test of F₁₉ cofactor, post 9 (2009)
G. Childers, compositeness test of F₁₉ cofactor, post 14 (2009)
S. Yamada, Fermat–Euler test of c_10,100,842 | F₂₅ cofactor, post 40 (2009)
A. T. Höglund, compositeness test of F₂₅ cofactor, post 51 (2009)
A. T. Höglund, compositeness test of c_20,201,768 | F₂₆ cofactor, post 62 (2009)
A. T. Höglund, compositeness test of c_40,403,531 | F₂₇ cofactor, post 64 (2010)
S. Yamada, Suyama test of c_1,262,577 | F₂₂ cofactor, post 70 (2010)

67. C. P. Wrathall, New factors of Fermat numbers, Math. Comp. 18 (1964), 324–325. MR 163868, DOI 10.1090/S0025-5718-1964-0163868-9
68. J. Young, D. A. Buell, The twentieth Fermat number is composite, Math. Comp. 50 (1988), 261–263. MR 917833, DOI 10.1090/S0025-5718-1988-0917833-8
69. Pseudonymous contributor ‘yorix’, Fermat cofactors, mersenneforum.org thread 17112, post 1 (2017), compositeness tests of c_10,100,842 | F₂₅ cofactor; with replies by:

G. B. Gostin, Fermat cofactor study, post 16 (2023)
G. B. Gostin, reply to other comments with an attachment of cofact_v0.6, post 18 (2023)
C. X. Cowie, Chronology of examining Fermat numbers or cofactors for compositeness, post 25 (2023)
G. B. Gostin, Suyama test of c_80,807,103 | F₂₈ cofactor, post 30 (2023); this comment also contains an updated version of cofact, v_0.8.
Pseudonymous contributor, Pépin and Suyama tests of F₂₉ and c_161,614,233 cofactor, post 41 (2023)

Vir Clarissime, Jam diu animadverti omnem numerum 2^{2^x+p} + 1, ubi x et p sint numeri integri, divisum per 2^{2^x} + 1 relinquere 2, propterea quod (2^{2^x} + 1) (2^{2^x} – 1) est = (2^{2^x+1} – 1), rursus (2^{2^x+1} – 1) (2^{2^x+1} + 1) = (2^{2^x+2} – 1) et sic porro, donec perveniatur ad 2^{2^x+p} – 1, qui numerus binario minor est quam 2^{2^x+p} + 1; ex eo quidem certe sequitur omnes numeros seriei Fermatianae esse inter se primos, ut dicis; at quantulum hoc est ad demonstrandum omnes illos numeros esse absolute primos?		Illustrious Sir, I noticed a long time ago that any number 2^{2^x+p} + 1, where x and p are integers, divided by 2^{2^x} + 1 leaves 2, because (2^{2^x} + 1) (2^{2^x} – 1) is = (2^{2^x+1} – 1), again (2^{2^x+1} – 1) (2^{2^x+1} + 1) = (2^{2^x+2} – 1) and so on, until we reach 2^{2^x+p} – 1, which is a binary number smaller than 2^{2^x+p} + 1; from this it certainly follows that all the numbers of the Fermatian series are prime to each other, as you say; but how much is this towards demonstrating that all those numbers are absolutely prime?
… Ob hoc ipsum exemplum a te allatum, magis quam antea dubito de veritate theorematis Fermatiani; fieri enim potest ut minimus divisor alicuius numeri 2^{2^x} + 1 sit centum, vel centies mille notarum, quem usque ad finem mundi nemo inveniat.		… Because of this very example brought by you, I doubt more than before the truth of Fermat’s theorem; for it is possible for the smallest divisor of any number 2^{2^x} + 1 to be a hundred, or a hundred thousand digits, which no one will find until the end of the world.
Christian Goldbach to Leonhard Euler, N.S. 31 July 1730 [24]

F_m – 2	= 2^{2^m} – 1 = (2^{2^m–1} – 1)·(2^{2^m–1} + 1) for any arbitrarily large m, since 2^m is divisible by 2;
	= (2^{2^m–2} – 1)·(2^{2^m–2} + 1) · F_m–1, since 2^m–1 is still divisible by 2;
	= … = (2^2¹ – 1)·(2^2¹ + 1) · F₂ · … · F_m–1; note, M₂ = 2²–1 = 3 = 2^2⁰+1 = F₀
∴ F_m	= F₀ · F₁ · F₂ · … · F_m–1 + 2

3. Mais voici ce que j’admire le plus : c’est que je suis quasi persuadé que tous les nombres progressifs augmentés de l’unité, desquels les exposants sont des nombres de la progression double, sont nombres premiers, comme		3. But here is what I admire most : it is that I am almost persuaded that all progressive numbers increased by one, whose exponents are numbers of the double progression, are prime numbers, such as
3 5 17 257 65537 4 294 967 297		3 5 17 257 65537 4 294 967 297
et le suivant de 20 lettres		and the next of 20 digits
18 446 744 073 709 551 617; etc.		18 446 744 073 709 551 617; etc.
Je n’en ai pas la démonstration exacte, mais j’ai exclu si grande quantité de diviseurs par démonstrations infaillibles, et j’ai de si grandes lumières, qui établissent ma pensée, que j’aurois peine à me dedire.		I do not have an exact demonstration, but I have excluded so many divisors by infallible demonstrations, and I have such great insights which establish my thoughts, that I would have trouble telling myself otherwise.
Pierre de Fermat to Bernard Frénicle de Bessy, August (or early September?) 1640 [22]

Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n’appréhendois d’être trop long.		And this proposition is generally true for all expressions and all prime numbers; of which I would send you the demonstration, if I were not afraid of going on too long.
Pierre de Fermat to Bernard Frénicle de Bessy, 18 October 1640 [22]

k	64k+1	k′	128k′+1	Character
1	65			composite
2	129	1	129	composite
3	193			prime
4	257	2	257	prime	= F₃; no Fermat number can divide another Fermat number (Goldbach’s theorem)
5	321			composite
6	385	3	385	composite
7	449			prime
8	513	4	513	composite
9	577			prime
10	641	5	641	prime	divides F₅
…	…	…	…
1,008	64,513	504	64,513	prime
…	…	…	…
1,017	65,089			prime
…	…	…	…
1,022	65,409	511	65,409	composite	largest value of k′ for smaller factor, 128k′+1 < √F₅
1,023	65,473			composite	largest value of k for smaller factor, 64k+1 < √F₅

(	107 2093 3158 0550 8180 4331 6350 5866 1999 4098	)x
+ (	34 1778 3881 0697 6545 8021 2127 5588 1034 4254	),

m	n	P_m mod 2³⁶	P_m mod 2³⁶ – 1	P_m mod 2³⁵ – 1
7	127	035100542404	514165207640	053153335617
8	255	531023263263	407614543114	344141643032
13	8,191	607301005536	611677367012	031455470517
14	16,383	622476273512	016631677043	161031465216
17	20	176536764625	415751561367	155276133751

m	Year	Cofactor	Prover
15	1984	c_9,856	H. Suyama [56]
12	1986	c_1,187	R. J. Baillie [61]
15	1987	c_9,840	H. Suyama [57]; R. J. Baillie [61]
16	1987	c_19,720	R. J. Baillie [61]
17	1987	c_39,444	R. J. Baillie [32]
11	1988	c₅₈₄	R. P. Brent [6]
11	1988	p₅₆₄	F. J. Morain [6]
18	1990	c_78,907	D. V. & G. V. Chudnovsky [62]
13	1991	c_2,436	A. K. Lenstra, W. Keller [30]
13	1991	c_2,417	R. E. Crandall [14]
19	1993	c_157,804	R. E. Crandall, J. Doenias, C. Norrie, J. Young [15]
21	1993	c_631,294	R. E. Crandall, J. Doenias, C. Norrie, J. Young [15]
13	1995	c_2,391	R. P. Brent [6,8]
16	1996	c_19,694	R. P. Brent & R. E. Crandall [8]
15	1997	c_9,808	R. P. Brent & R. E. Crandall [8]
18	1999	c_78,884	R. E. Crandall [32]

n	P₂₂ mod 2³⁶	P₂₂ mod 2³⁶ – 1	P₂₂ mod 2³⁵ – 1
126000	14541047264	62070375509	27381595983
354000	45744331640	37262695986	30266592884
486000	24041343749	49018090515	1797017786
790000	66015459363	57091562477	29124348244
1078000	41097905003	41183234167	18395262145
1430000	37800690011	17322513532	30657148115
1854000	13706770442	2076479040	105211355
2390000	39355539574	67554578594	23663736438
2718000	45076516494	67299003714	535858315
3046000	397350536	19533135442	15348306
3542000	10838294599	41096201992	14648574810
3838000	4342596189	27597863567	31241328256
4182000	49032769250	16910406249	26122490955

m	A_m mod C mod 2¹⁶	B_m mod C mod 2¹⁶	cofact A_m mod C mod 2¹⁶	cofact B_m mod C mod 2¹⁶
19	51945	14357	CAE9₁₆ = 51945	3815₁₆ = 14357
21	41530	40393	A23A₁₆ = 41530	9DC9₁₆ = 40393

modulus		P₂₄ residue
2³⁶		60450279532
2³⁶–1		68627742455
2³⁵–1		32898231088
2⁶⁴		17311B7E131E106C₁₆ = 1671147165031731308₁₀

m	Date	Cofactor	Residue mod 2⁶⁴	Prover(s)
19	17 July 2009	c_157,770	C61CCF4C8ABEF914	J. R. King.; A. Kruppa; G. Childers et al. [66]
25	23 July 2009	c_10,100,842	44BFC8D231602007	S. Yamada (Fermat–Euler test) [66]; A. T. Höglund [66]; and in 2022, E. W. Mayer [41]
26	3 Aug 2009	c_20,201,768	6C433D4E3CC9522E	A. T. Höglund [66]; and in 2022, E. W. Mayer [41]
14	3 Feb 2010	c_4,880	(no residue given)	W. B. Lipp; R. D. Silverman; T. Rajala; P. Moore (Suyama test) [49]
22	27 Mar 2010	c_1,262,577	BEAE94F64C12B741	D. Domanov [18]; S. Yamada (Suyama test) [66]
12	27 Mar 2010	c_1,133	(no residue given)	M. Vang; S. Batalov [60]
27	4 Apr 2010	c_40,403,531	481F26965DE16117	A. T. Höglund [66]; and in 2022, E. W. Mayer [41]
17	15 Mar 2011	c_39,395	6EF4AD31682CD751	D. Chia; T. Sorbera [1]
28	12 May 2022	c_80,807,103	790BE051D73D667E	E. W. Mayer [41]; and in 2023, G. B. Gostin [69]
29	12 May 2022	c_161,614,233	AB3DBCEFFE907786	E. W. Mayer [41]; and in 2023, R. Propper
30	12 May 2022	c_323,228,467	EDFCE7FC50271D44	E. W. Mayer [41]

m	P_m mod 2⁶⁴ (hex)	P_m mod 2³⁶	P_m mod 2³⁶–1	P_m mod 2³⁵–1	A_m mod 2⁶⁴ (hex)	A_m mod 2³⁶	A_m mod 2³⁶–1	A_m mod 2³⁵–1	B_m mod 2⁶⁴ (hex)	B_m mod 2³⁶	B_m mod 2³⁶–1	B_m mod 2³⁵–1	S_m mod 2⁶⁴ (hex)	S_m mod 2³⁶	S_m mod 2³⁶–1	S_m mod 2³⁵–1	gcd (A_m – B_m, C)
0	Neither the Pépin test nor the Suyama test may be applied to the zeroth Fermat number
1–4	–1	–1	–1	–1	1	1	1	1	These Fermat numbers are prime, so the Suyama test is not required
5	9D894F	10324303	10324303	10324303	B48B4570	3029026160	3029026160	3029026160	}	Fermat numbers F₅ to F₁₁ are completely factored, so the Suyama test is not required
6	A497F7120F395E35	8845352501	9017941414	9190530327	79763C94C301A5F2	20451534322	20578896315	20706258308
7	95984E80E902C504	3909272836	44591026080	5799525263	7C36D29F9594A24B	66934055499	8117436329	34344873225
8	6507E50AC84D66B3	46310188723	35403253324	30627284506	BD369DB0333BDAB9	859560633	49398862793	7169939333
9	B8E74A7493EECD76	19661770102	54966870189	28173182079	C92C3A1A3EFD953C	44006479164	9621194327	19262051920
10	E035DD28798E8098	36399120536	54182679152	28022031617	D8FD758BF8EF405D	51421069405	27332107831	16611700203
11	38AD5BCF85A1DD28	66666487080	44928212591	3934743084	2F2F83E6A14C7C3A	28475948090	45109638561	22705527920
12	06C3171F0746A313	64546579219	3387502849	5300454051	8346D942AF82520A	11534488074	48121973657	11150519550	98D29BB505C82D27	21571841319	31828999134	249760013	06D3316513FC3333	21810131763	65765080811	7388471481	1
13	D79356EC3B040B5E	52529728350	52864871946	3434508623	4B3EA30710A4989A	30343993498	52451231872	9804790336	4F2A986CE8427164	55436276068	19383040962	1680477711	E77153C999263C25	41224125477	2496190587	25908858272	1
14	CC52BC3C94F9774A	54038984522	1986493987	15173315214	E110B2DF4898DFD7	65642487767	21972275522	32620083537	96D8E2B802C733B3	34406347699	24532874398	27969365260	FC6DCDF563F934D2	23152112850	20505684606	16876703551	1
15	D534BCF1A89FCA9F	7124011679	42435904961	14110954287	46C3D48B9041D9E3	49664874979	4867942482	25174316024	7F08E8A9EEFDD710	42664318736	28937048602	22628990761	167C0419066997DF	38762289119	67988866249	9771151649	1
16	40ABB0C5BFF05CB5	24695037109	65390296136	173595305	7A3617ECEEB13091	55544197265	25060016989	20710633406	DFBA3FBD0A4A225A	56007205466	26702937368	29834196943	02664CA2851BBDCA	10823122378	38394099743	763967994	1
17	5AFC1FE36DC81DDD	14726733277	2770550506	14982977589	907B654AA857D7A8	45774002088	22659343630	9924649749	BEDA5B4F3DC4EADD	65460824797	63727741388	5932131125	8EF31C72B0209FF0	11544862704	30808052802	15101673067	1
18	506A5A0ABC27E6F0	46106404592	14070013587	10874364700	BCBFB1C446912EAD	18363788973	16198816711	5160281264	689AC15EAF3057EE	63068723182	29076663800	15794027617	CC9626F5A95549B1	24315775409	41329922521	4867623401	1
19	8C9339452E75F19C	22254317980	58676148574	6407009455	449FBCA640B4FA27	26855406119	30933529616	405458041	4E81A5FE01B9AC83	60158487683	52398778242	18465526654	14103D7C8A6FDF38	53862195000	27723811980	23470815198	1
20	78791573ED3DE5F1	16865158641	35626292569	15265819636	11BEF945BB1F0767	24614209383	29963929564	26085093865	This Fermat number has no known factors, so the Suyama test cannot proceed
21	C4AE66D539B41B40	22442941248	300257643	30981963597	A07023647D42B4D5	19281392853	11280367853	12351604643	DA11FF47C9F2DBA7	33452907431	25506585220	5803823552	1A6B2145AEB90471	24406197361	18942332167	15719707512	1
22	77F6FA403A09D72A	973723434	8733349067	12323430823	1B7A892DC7F0EC35	59189029941	62994050515	21359120063	F2F13497115814AD	30355756205	58598662170	31225537268	8F2B6FC5AA6AF96A	24333973866	30570899199	5450609407	1
23	50E1F11B55196BBB	48672369595	60596902712	4259642653	14E2143DD7E57ABB	59456715451	10275710011	27248444876	1029BE52A5446CDA	11362659546	54792073816	3050368568	5574287CB97265BA	54650889658	13707222996	8874908179	1
24	17311B7E131E106C	60450279532	68627742455	32898231088	6EC4A4806BE07FAA	1809874858	49220810423	7419597027	This Fermat number has no known factors, so the Suyama test cannot proceed
25	CB913B6E3B1FFE2A	61121494570	15369168494	9073733940	7B6B087B84A45562	49470002530	66886679148	26994100025	2909830729BFA110	30765195536	21153567739	30348546187	7A551893ACF4BE4E	15786622542	65496009072	34178045549	1
26	2B58BDE2A0C14045	11286954053	2307231107	9689287987	FBB406B3A281838C	15611298700	7371940776	2193939191	25F5AB0FFC728C87	68659874951	20444894301	32173443562	B7BD14979ACF222E	32662037038	15466936163	6416457631	1
27	043A6C8B9272B297	49701630615	39732934618	30710305624	C3B191C45CCD7820	18736838688	55240256170	21887650168	485F292142F953EC	5418603500	26481669619	20036545122	79E89190C56372B7	3311628983	29330680430	2608954171	1
28	468731C3E6F13E8F	16759471759	9104636564	30476727665	7CAE1275B362B2CA	24484426442	30894284803	20461105324	BD496177DB5155A0	33744311712	3778945069	33633822046	790BE051D73D667E	7906092670	55362539930	4159568998	1
29	BECE1E5FFBE5EC12	68650658834	21246329964	17796269382	9BD416DB3918C152	48202563922	58920206666	32748692453	30AFC6010F62884B	4553082955	6544795868	7473784009	AB3DBCEFFE907786	68695390086	41564307636	13349243207	1
30	A70C2A3DB98D6D9D	58947628445	59810773698	26425548225	1D7AA56A5428333C	44361593660	40327643421	30698378043	6F856680482D3F4E	1210924878	48656226334	9072042323	EDFCE7FC50271D44	52884348228	34401987830	9723857098	1

F_m	Factorisation	Character, known factors	Year	Discoverer(s) / Prover(s)	Event
F₀ F₁ F₂ F₃ F₄	= p₁ } = p₁ } = p₂ } = p₃ } = p₅ }	prime	1640	Fermat [22, op. cit.]	All Fermat numbers F_m asserted to be prime
These are the only known Fermat primes. At some point in the two decades after 1640, Fermat claimed to have a proof of primality for all Fermat numbers using his method of infinite descent, only to subsequently discover that his proof was faulty. He appears to have nevertheless believed his conjecture to be true, and highly desired that someone would improve the proof to clinch the result; for instance in 1654 he wrote to Pascal attempting to interest him in the problem, and as late as 1658 he is writing to an English correspondent, Kenelm Digby.
F₅	= p*₁₀	prime*	1640	Fermat [22]	Claimed to be prime
	= p₃ · u₇	2 factors, 1 definitely prime	1732	Euler [20]	Discovery of p₃ factor
	= p₃ · p₇	semiprime, completely factored	?	Euler	Primality of p₇ cofactor shown
Euler discovered the first Fermat factor by [O.S.] 26 September 1732, the date of his lecture to the Saint Petersburg Academy. What is not clear is how quickly he came to discover that the 7-digit cofactor was also prime (a task some 25 times smaller than the potential worst case trial division of F₅). The previous largest known prime was Ibn Fallûs / Pietro Cataldi’s M₁₉ = 524,287, so the cofactor would have been the new largest known prime until Euler’s own proof of the primality of M₃₁.
F₆	= p*₂₀	prime*	1640	Fermat [22]	Claimed to be prime
	= u₂₀	unknown	1732	Euler [20]	Factorisation of F₅ disproved Fermat’s conjecture
	= p₆ · p*₁₄	semiprime*	1855	Clausen [2]	Complete factorisation claimed
	= c₂₀	composite	1877	Lucas [38]	Compositeness test (Pell subsequence), Lucas being unaware of Clausen’s factorisation
	= p₆ · u₁₄	2 factors, 1 definitely prime	1880	Landry [34]	Rediscovery of first p₆ factor
	= p₆ · p₁₄	semiprime, completely factored	1880	Landry, Le Lasseur [40]	Primality of p₁₄ cofactor shown
Clausen’s 1 January 1855 letter to Gauss claimed both factors to be prime, without proof. He wrote, »Auch habe ich gefunden, daß die Zahl 2⁶⁴+1 in die beiden Primfactoren 274177 und 67280421310721 zerlegt werden kann; die letzere ist, so viel ich weiß, die größte bis jetzt bekannte Primzahl.« (“Also I have found that the number 2⁶⁴+1 can be broken into two prime factors 274177 and 67280421310721; the latter is, so far as I know, the largest known prime number.”) For F₇ and following, we will omit the first two chronological events, that in 1640 Fermat believed all Fermat numbers to be prime, whereas Euler disproved the conjecture in 1732 by finding the first Fermat divisor.
F₇	= c₃₉	composite	1905	Morehead [43]; Western [64]; 1952, Robinson [52]	Pépin tests showed F₇ to be composite
F₇	= p₁₇ · p₂₂	semiprime, completely factored	1970	Morrison & Brillhart [45,46]	Fermat number decomposed into two prime factors
Strictly speaking Morrison and Brillhart’s factorisation broke F₇ into two numbers of unknown character, which were both found to be prime. Compare F₉ below.
F₈	= c₇₈	composite	1909	Morehead & Western [44]; 1952, Robinson [52]	Pépin test showed F₈ to be composite
	= p₁₆ · p*₆₂	2 factors, 1 definitely prime	1980	Brent & Pollard [9]	Discovery of first prime factor
	= p₁₆ · p₆₂	semiprime, completely factored	1980	Williams [9]	Proof of p₆₂ cofactor’s primality
Brent and Pollard strongly suspected p*₆₂ to be prime after it passed about 100 Rabin tests.
F₉	= p₇ · u₁₄₈	1 prime factor	1903	Western [17]	Discovery of first prime factor
	= p₇ · c₁₄₈	1 prime factor, composite cofactor	1967	Brillhart [28]	Cofactor shown to be composite
	= p₇ · p₄₉ · p₉₉	3 factors, 1 definitely prime	1990	Lenstra, Lenstra, Manasse, & Pollard [36]	Cofactor split into 2 probably prime factors
	= p₇ · p₄₉ · p₉₉	3 prime factors, completely factored	1990	Odłyżko [36]	New factors proven to be prime

F₁₀	= c₃₀₉	composite	1952	Robinson [52]; 1953, Lehmer [52]; 1960, Paxson [47]	Pépin tests showed F₁₀ to be composite
	= p₈ · u₃₀₁	1 prime factor	1953	Selfridge [52,54]	Discovery of first prime factor
	= p₈ · p₁₀ · u₂₉₁	2 prime factors	1962	Brillhart [11]	Discovery of second prime factor
	= p₈ · p₁₀ · c₂₉₁	2 prime factors, composite cofactor	1967	Brillhart [28]	Cofactor shown to be composite
	= p₈ · p₁₀ · p₄₀ · p₂₅₂	4 prime factors, completely factored	1995	Brent [6,7]	Discovery of third factor, primality proof of p₂₅₂ cofactor

F₁₁	= p₆ · p′₆ · u₆₀₆	2 prime factors	1899	Cunningham [17]	Discovery of two prime factors
	= p₆ · p′₆ · c₆₀₆	2 prime factors, composite cofactor	1970s	Wagstaff [25]	Cofactor shown to be composite
	= p₆ · p′₆ · p₂₂ · c₅₈₄	3 prime factors, composite cofactor	1988	Brent [5,6]	Discovery of third factor, cofactor composite
	= p₆ · p′₆ · p₂₂ · p₂₁ · p*₅₆₄	5 factors, 4 definitely prime	1988	Brent [5,6]	Discovery of fourth factor, cofactor probably prime
	= p₆ · p′₆ · p₂₂ · p₂₁ · p₅₆₄	5 prime factors, completely factored	1988	Morain [5,6]	Proof of p₅₆₄ cofactor’s primality
This is the largest Fermat number to be completely factored, but was not the most recent, due to the size of the second-largest factor p₂₂ making it much easier to discover than p₄₀ \| F₁₀ or p₄₉ \| F₉.
F₁₂	= p₆ · u_1,228	1 prime factor	1877	Pervushin [3]; 1878, Lucas [4,39]	Discovery of first prime factor
	= p₆ · p₈ · p′₈ · u_1,213	3 prime factors	1903	Western [17]	Discovery of two prime factors
	= p₆ · p₈ · p′₈ · p₁₂ · u_1,202	4 prime factors	1974	Hallyburton & Brillhart [28]	Discovery of fourth prime factor
	= p₆ · p₈ · p′₈ · p₁₂ · c_1,202	4 prime factors, composite cofactor	1970s	Wagstaff [25]	Cofactor shown to be composite
	= p₆ · p₈ · p′₈ · p₁₂ · p₁₆ · c_1,187	5 prime factors, composite cofactor	1986	Baillie [61]	Discovery of fifth factor, cofactor composite
	= p₆ · p₈ · p′₈ · p₁₂ · p₁₆ · p₅₄ · c_1,133	6 prime factors, composite cofactor	2010	Vang [60] (cofactor: also Batalov, Schindel)	Discovery of sixth factor, cofactor composite
The version of the GMP-ECM program by Paul Zimmerman and customised by Alex Kruppa, which Mike Vang used to find the sixth known prime factor, ran a compositeness test on the cofactor immediately after discovering the factor. Compositeness was verified by Serge Batalov and others.
F₁₃	= c_2,467	composite	1960	Paxson [47]; 1961, Hurwitz & Selfridge [55]	Pépin tests showed F₁₃ to be composite
	= p₁₃ · u_2,454	1 prime factor	1974	Hallyburton & Brillhart [28]	Discovery of first prime factor
	= p₁₃ · c_2,454	1 prime factor, composite cofactor	1970s	Wagstaff [25]	Cofactor shown to be composite
	= p₁₃ · p₁₉ · u_2,436	2 prime factors	1991	Crandall [14]	Discovery of second prime factor
	= p₁₃ · p₁₉ · c_2,436	2 prime factors, composite cofactor	1991	Lenstra; Keller [30]	Cofactor shown to be composite
	= p₁₃ · p₁₉ · p′₁₉ · c_2,417	3 prime factors, composite cofactor	1991	Crandall [14]	Discovery of third factor, cofactor composite
	= p₁₃ · p₁₉ · p′₁₉ · p₂₇ · c_2,391	4 prime factors, composite cofactor	1995	Brent [6,8]	Discovery of fourth factor, cofactor composite

F₁₄	= c_4,933	composite	1961	Hurwitz & Selfridge [29,55]; 1987, Young & Buell [68]	Pépin test showed F₁₄ to be composite
F₁₄	= p₅₄ · c_4,880	1 prime factor, composite cofactor	2010	Rajala [49] (cofactor: also Lipp; Silverman; Moore)	Discovery of first factor, cofactor composite

F₁₅	= p₁₀ · u_9,856	1 prime factor	1925	Kraïtchik [33]	Discovery of first prime factor
	= p₁₀ · c_9,856	1 prime factor, composite cofactor	1984	Suyama [56]	Cofactor shown to be composite
	= p₁₀ · p₁₆ · u_9,840	2 prime factors	1987	Gostin [26]	Discovery of second prime factor
	= p₁₀ · p₁₆ · c_9,840	2 prime factors, composite cofactor	1987	Suyama [57]; Baillie [61]	New cofactor; still composite
	= p₁₀ · p₁₆ · p₃₃ · u_9,808	3 prime factors	1997	Crandall & van Halewyn [8]	Discovery of third prime factor
	= p₁₀ · p₁₆ · p₃₃ · c_9,808	3 prime factors, composite cofactor	1997	Crandall & Brent [8]	New cofactor also composite

F₁₆	= p₉ · u_19,720	1 prime factor	1953	Selfridge [52,54]	Discovery of first prime factor
	= p₉ · c_19,720	1 prime factor, composite cofactor	1987	Baillie [61]	Cofactor shown to be composite
	= p₉ · p₂₇ · u_19,694	2 prime factors	1996	Crandall & Dilcher [8]	Discovery of second prime factor
	= p₉ · p₂₇ · c_19,694	2 prime factors, composite cofactor	1996	Brent & Crandall [8]	New cofactor also composite

F₁₇	= p₁₄ · u_39,444	1 prime factor	1978	Gostin [25]	Discovery of first prime factor
	= p₁₄ · c_39,444	1 prime factor, composite cofactor	1987	Baillie [32]	Cofactor shown to be composite
	= p₁₄ · p₄₉ · u_39,395	2 prime factors	2011	Bessell [1]	Discovery of second prime factor
	= p₁₄ · p₄₉ · c_39,395	2 prime factors, composite cofactor	2011	Chia; Sorbera [1]	New cofactor also composite

F₁₈	= p₈ · u_78,907	1 prime factor	1903	Western [17]	Discovery of first prime factor
	= p₈ · c_78,907	1 prime factor, composite cofactor	1990	Chudnovsky twins [62]	Cofactor shown to be composite
	= p₈ · p₂₃ · u_78,884	2 prime factors	1996	Crandall, McIntosh, & Tardif [8]	Discovery of second prime factor
	= p₈ · p₂₃ · c_78,884	2 prime factors, composite cofactor	1999	Crandall [32]	New cofactor also composite

F₁₉	= p₁₁ · u_157,816	1 prime factor	1962	Riesel [51]	Discovery of first prime factor
	= p₁₁ · p₁₂ · u_157,804	2 prime factors	1963	Wrathall [67]	Discovery of second prime factor
	= p₁₁ · p₁₂ · c_157,804	2 prime factors, composite cofactor	1993	Crandall, Doenias, Norrie, & Young [15]	Cofactor shown to be composite
	= p₁₁ · p₁₂ · p₃₅ · u_157,770	3 prime factors	2009	Bessell [66]	Discovery of third prime factor
	= p₁₁ · p₁₂ · p₃₅ · c_157,770	3 prime factors, composite cofactor	2009	King; Kruppa; Childers [66]	New cofactor also composite

F₂₀	= c_315,653	composite	1987	Young & Buell [68]; 1993, Crandall, Doenias, Norrie, & Young [15]	Pépin tests showed F₂₀ to be composite

F₂₁	= p₁₃ · u_631,294	1 prime factor	1963	Wrathall [67]	Discovery of first prime factor
F₂₁	= p₁₃ · c_631,294	1 prime factor, composite cofactor	1993	Crandall, Doenias, Norrie, & Young [15]	Cofactor shown to be composite

F₂₂	= c_1,262,612	composite	1993	Crandall, Doenias, Norrie, & Young [15]; Trevisan & Carvalho [58]; 1999, Crandall et al. [16]	Pépin tests showed F₂₂ to be composite
	= p₃₅ · u_1,262,577	1 prime factor	2010	Bessell [18]	Discovery of first prime factor
	= p₃₅ · c_1,262,577	1 prime factor, composite cofactor	2010	Domanov [18]; Yamada [66]	Cofactor shown to be composite

F₂₃	= p₉ · u_2,525,215	1 prime factor	1878	Pervushin [4]	Discovery of first prime factor
F₂₃	= p₉ · c_2,525,215	1 prime factor, composite cofactor	2000	Crandall, Mayer, & Papadopoulos [16]	Cofactor shown to be composite

F₂₄	= c_5,050,446	composite	1999	Crandall, Mayer, & Papadopoulos [16]	Pépin tests showed F₂₄ to be composite

F₂₅	= p₁₄ · u_10,100,878	1 prime factor	1963	Wrathall [67]	Discovery of first prime factor
	= p₁₄ · p₁₈ · u_10,100,860	2 prime factors	1985	Gostin [26]	Discovery of second prime factor
	= p₁₄ · p₁₈ · p₁₉ · u_10,100,842	3 prime factors	1987	McLaughlin [12]	Discovery of third prime factor
	= p₁₄ · p₁₈ · p₁₉ · c_10,100,842	3 prime factors, composite cofactor	2009	Yamada [66]; Höglund [66]	Cofactor shown to be composite

F₂₆	= p₁₄ · u_20,201,768	1 prime factor	1963	Wrathall [67]	Discovery of first prime factor
F₂₆	= p₁₄ · c_20,201,768	1 prime factor, composite cofactor	2009	Höglund [66]; 2022, Mayer [41]	Cofactor shown to be composite

F₂₇	= p₁₅ · u_40,403,548	1 prime factor	1963	Wrathall [67]	Discovery of first prime factor
	= p₁₅ · p₁₈ · u_40,403,531	2 prime factors	1985	Gostin [26]	Discovery of second prime factor
	= p₁₅ · p₁₈ · c_40,403,531	2 prime factors, composite cofactor	2010	Höglund [66]; 2022, Mayer [41]	Cofactor shown to be composite

F₂₈	= p₂₂ · u_80,807,103	1 prime factor	1997	Taura [16]	Discovery of first prime factor
F₂₈	= p₂₂ · c_80,807,103	1 prime factor, composite cofactor	2022	Mayer [41]; 2023, Gostin [69]	Cofactor shown to be composite

F₂₉	= p₁₆ · u_161,614,233	1 prime factor	1980	Gostin & McLaughlin [27]	Discovery of first prime factor
F₂₉	= p₁₆ · c_161,614,233	1 prime factor, composite cofactor	2022	Mayer [41]	Cofactor shown to be composite

F₃₀	= p₁₅ · p₁₆ · u_323,228,467	2 prime factors	1963	Wrathall [67]	Discovery of first two prime factors
F₃₀	= p₁₅ · p₁₆ · c_323,228,467	2 prime factors, composite cofactor	2022	Mayer [41]	Cofactor shown to be composite