The Largest Known prime by Year: A Brief History (original) (raw)

By Chris Caldwell

The largest known prime today is the 41,024,320 digit Mersenne prime 2136279841-1 found in October 2024, but how big have the "largest known primes" been historically? Historically, how have these primes been found? We will briefly discuss each of these questions below.

Contents

1. Before Electronic Computers
   • Table of the Record Prime by Year
2. The Age of Electronic Computers
   • Graph of the Record Prime by Year
   • Table of the Record Prime by Year
3. Epilogue: No more predictions
   • The First Billion Digit Prime

[](#contents) Part One: Before Electronic Computers

For information on the French Monk Marin Mersenne's prime conjecture and its errors, see this link

Many early writers felt (incorrectly) that if p was prime, then so was M_p_ = 2_p_-1. These numbers, now called the Mersenne Numbers, were the focus of most of the early searches for large primes. The early history of these numbers is strewn with many false claims of primality, even by such notables as Mersenne, Leibniz, and Euler. So we give credit to our first record holder with some doubt:

by 1588 Pietro Cataldi had correctly verified that 217-1 = 131071 and 219-1 = 524287 are both prime [Cataldi1603].

But Cataldi also had incorrectly stated 2_n_-1 was also prime for each of 23, 29, 31 and 37. This is interesting because Cataldi made his discoveries by constructing what Shanks calls "the first extensive table of primes--up to 750" [Shanks78, p14]. These tables are big enough to show 219-1 is prime (its square root is approximately 724) but not large enough to handle these four larger numbers!

Note: Some writers (e.g., [Picutti1989] and [BS96, p309]) include the primes 8191=213-1 (before 1458, Codice Palatino 573) and 131071=217-1 (1460, Codex Ottb. Lat 3307) in their list of records. But we omit them for lack of evidence that they were proven primes at that time, rather than just lucky guesses.

In 1640 Fermat showed that if p is an odd prime, then all prime divisors of 2_p_-1 have the form 2_kp_+1. He then quickly showed Cataldi was wrong about 23 (which has the factor 47 with _k_=1) and 37 (factor 223 at _k_=3). Finally, in 1738, Euler showed Cataldi was also wrong about 29 by finding the divisor 233. Here, using Fermat's result, _k_=4. This is just the second number to try using Fermat's result as _k_=2 and _k_=3 yield composites (so I would guess Fermat also knew of this factor). Note that Cataldi's errors were shown with small factors found in Cataldi's own table of primes, and none took more than two trial divisions!

Euler gives us the first clear record (except perhaps for the date) by proving Cataldi was correct about 31:

by 1772 Euler had used clever reasoning and trial division to show 231-1 = 2147483647 is prime.

The actual date must be between 28 October 1752 when Euler sent a letter to Goldbach [text from Euler Archive] stating that he was uncertain about this number (even though he had earlier listed it as prime) and 1772 when a letter [text] was published from Euler to Bernoulli stating he proved 231-1 prime by showing all prime divisors of 231-1 must have one of the two forms 248_n_+1 and 248_n_+63, and then dividing by all such primes less than 46339 [Dickson19, pp18-19]. This requires a simple theorem which is stronger than Fermat's result above. (Euler had listed 231-1 a prime as early as 1732, but he did so along with 241-1 and 247-1 both of which were composite [translation].)

Note: Some writers (e.g., [BS96, p309]) include the primes 999999000001 (1851, "found" by Looff) and 67280421310721 (1 Jan. 1855, Clausen) in their tables. The first appeared in a table of Looff with a question mark, but Reuschle [Reuschle1856, pp.3,18] claims Looff had proved it prime. Thomas Clausen provided the factorization 274177 · 67280421310721 of 264+1 in a letter to Gauss dated 1 Jan 1855 stating both factors were prime [Biermann1964]. But it remains a claim without a method.

By 1867 Landry had found a larger prime, still by trial division, as a factor of 259-1 (namely (259-1)/179951 = 3203431780337), this prime held the record longer than any other non-Mersenne would (before or after his discovery). However all such efforts were to be eclipsed by a new mathematical discovery, so we pause for a moment to summarize all record primes (that I know about) before modern computers. (In the long run, it is always the mathematics that decide how large of prime we can find.)

Table 1. Records before Electronic Computers

By 1876 Lucas had developed a clever test to determine if Mersenne numbers were prime. His method was later made even simpler by Lehmer in the 1930's, and is still used to discover the record primes!

In 1876 Lucas proved that 2127-1 = 170141183460469231731687303715884105727 was prime.

"This remained the largest known prime until 1951" [HW79, p16] And this record, which stood for 75 years, may stand forever as the largest prime found by hand calculations.

In 1951 Ferrier used a mechanical desk calculator and techniques based on partial inverses of Fermat's little theorem (see the pages on finding and proving primes) to slightly better this record by finding a 44 digit prime:

In 1951 Ferrier found the prime (2148+1)/17 = 20988936657440586486151264256610222593863921.

With this record we end the period before electronic computers, for in this same year a new record of 79 digits was to be set by computer.

Note: It is quite difficult to place Ferrier's discovery among Miller & Wheeler's chronologically. We follow the traditional order and put Ferrier's first, but there is good reason to doubt this.

For more information see The History of the Theory of Numbers by Leonard Dickson [Dickson19].

[](#contents) Part Two: The Age of Electronic Computers

In 1951 Miller and Wheeler began the electronic computing age by finding several primes:

k.M127 + 1 for k = 114, 124, 388, 408, 498, 696, 738, 774, 780, 934 and 978

as well as the new 79 digit record:

180(M127)2+1 (here M127 = 2127-1) [MW51].

This record was soon eclipsed by Raphael Robinson's discoveries of five new Mersennes the very next year using the SWAC (Standards Western Automatic Computer). This was the first program that Robinson had ever written, and it ran the very first time he tried it! Not only that, but his program found two new record primes that very day! He writes [Robinson54]:

The program was first tried on the SWAC on January 30, and two new primes were found that day [M521, M607], three other primes were found on June 25 [M1279], October 7 [M2203] and October 9 [M2281].

It is interesting to note that in 1949 the topologist M. H. A Newman used the prototype Manchester electronic computer (with 1024 bits of storage) to make the first attempt to find Mersenne primes by computer. Perhaps because Alan Turing worked on this machine from 1948 to 1950, and improved the program by Newman, this first attempt at finding primes by (electronic) computers is sometimes attributed to him (e.g., [Robinson54] and [Ribenboim95, p93]). The excellent Alan Turing Internet Scrapbook has a picture of this machine.

We see the records of Miller, Wheeler, and Robinson as the first points on the following graph--note the vertical scale!

Progress over the next few years was as steady as the increase in speed of computers. Riesel found M3217 using the Swedish machine BESK; Hurwitz found M4253 and M4423 using an IBM 7090 (see next paragraph); Gillies used the ILLIAC-2 to find M9689, M9941 and M11213. Tuckerman found M19937 using an IBM360.

Surprisingly Hurwitz knew about M4423 seconds before M4253 (because of the way the output was stacked). John Selfridge asked "Does a machine result need to be observed by a human before it can be said to be 'discovered'?" To which Hurwitz replied, "forgetting about whether the computer knew, what if the computer operator who piled up the output looked?" In the table below I decided that Hurwitz discovered the prime when he read the output, so M4253 was never the largest known prime.

Table 2. Records by Electronic Computer

Curiously the prime M74207281 was detected by a machine months before a human noticed it--see the press release for this prime.

All of the Mersenne records were found using the Lucas-Lehmer test and the other two were found using Proth's Theorem (or similar results). The Amdahl Six is J Brown, C Noll, B Parady, G Smith, J Smith and S Zarantonello.

[](#contents) Epilogue: No Predictions

When will we have a one billion digit prime? Good question! In the early days of the GIMPS search, my predictions were reasonable, but recently things have taken a turn (see the graph) that defies prediction using simple regressions and past history. My last prediction was way off!

I am getting out of the time prediction business. So we will end with a linear graph and a gratuitous cubic below. Useful future predictions should be based not only on heuristics such as found on the page Where is the Next Mersenne?, but should also track the usage data for projects like GIMPS. It is the current participants, not the past, which will find the next prime.

Printed from the PrimePages <t5k.org> © Reginald McLean.