Is 170,141,183,460,469,231,731,687,303,715,884,105,727 prime? Before you ask the Internet for an answer, can you consider how you might answer that question without a computer or even a digital calculator?
In the 1800s French mathematician Édouard Lucas spent years proving that this 39-digit number was indeed prime. How did he do it? Lucas, who incidentally also designed the entertaining game Tower of Hanoi, developed a method that’s still useful today, more than a century later.
People have been fascinated by prime numbers for millennia. These numbers are divisible only by 1 and themselves, whereas every other integer can be uniquely expressed as the product of several prime numbers; for example, 15 = 3 × 5. Prime numbers essentially form the periodic table of mathematics. They also hold many secrets. They appear on the number line with a certain regularity, but their occurrence is characterized by fluctuations that cannot yet be quantified. This unpredictability has been a source of consternation for experts.
On supporting science journalism
If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
And math enthusiasts are constantly seeking new prime numbers. The current record (as of October 2025) for the largest prime is 2136,279,841 − 1, a number with 41,024,320 digits. Simply reading this number aloud would take approximately 240 days.
Prime Numbers with a Special Structure
Anyone who has observed the record-breaking prime numbers of recent years may have noticed that they mostly have a similar structure: 2p – 1 (where p is a prime number). Prime numbers of this form are called Mersenne primes. And the number to which Lucas dedicated almost two decades of his life is also a Mersenne prime, namely 2127 – 1. But there’s some trickiness to these Mersenne primes: not every 2p– 1 is a prime number for every prime value of p. For example, 211 – 1 yields 2,047 and can be written as the product of 23 and 89.
So in the mid-19th century Lucas wondered whether 2127 – 1 was prime or not. He faced a formidable challenge. The number is enormous, consisting of 39 digits, and at that time Lucas obviously didn’t have access to a computer. He had to manually ensure that 2127 – 1 had no divisors (except 1 and itself).
One way to accomplish this feat is to go through all prime numbers up to 2127 – 1 and make sure it does not divide by any of them. But this is extremely time-consuming and simply infeasible if you don’t know all the smaller prime numbers.
The Lucas-Lehmer Prime Number Test
Lucas didn’t give up. He developed a novel method based on the findings of his colleague Évariste Galois that required significantly less computation.
Before we delve into the beautiful—but admittedly abstract—mathematics of Galois and Lucas, I’ll present Lucas’s result, now known as the Lucas-Lehmer primality test.
To check whether 2p – 1 is prime, Lucas developed the following algorithm:
Create a sequence of numbers whose first term is s0 = 4 and where each subsequent sn is calculated as s2n – 1 – 2. The sequence is therefore: 4, 14, 194, 37,634, and so on.
Then 2p – 1 is a prime number if and only if the p – 2nd term of the sequence (that is, sp – 2) is divisible by 2p – 1 without a remainder. That is to say, every Mersenne prime has this property, and conversely, every sp – 2 defines a Mersenne prime 2p – 1.
So instead of dividing the Mersenne number by all prime numbers less than 2127 – 1, it suffices to perform calculations to determine s125 and then divide by 2127 – 1. That’s much simpler, right?
In practice, there’s just one tiny—or rather, very big—problem. The sequence terms sn grow extremely fast—so fast, in fact, that it’s not particularly practical to work with them. Therefore, experts resort to a trick: they divide the sequence terms sn by the Mersenne number and continue with the remainder if the division doesn’t result in a whole number. This doesn’t change the second part of the algorithm, so the condition for Mersenne primes remains the same: they must be able to evenly divide sp – 2. This trick does make sp – 2 significantly smaller, however.
To better understand the primality test, we can work through it using a simple example: the Mersenne number 2⁵ – 1, which is 31. Using the algorithm developed by Lucas, we need to calculate s3, which is 37,634. Dividing this number by 31 gives us the exact result 1,214. This means that s3 is divisible by 25 – 1, and therefore, the latter is a prime number.
After years of painstaking work, Lucas developed this primality test and applied it to 2127 – 1. He was thus able to show that it was indeed a prime number. To this day, it remains the largest prime number found without the aid of a computer.
Lucas did not conclusively prove that his method reliably identified Mersenne primes, however. This was only achieved by mathematician Derrick Henry Lehmer in 1930, which is why the method is known as the Lucas-Lehmer primality test.
Finite Number Sets
But why does this strategy work at all? In fact, the proof is quite technical—and therefore, I’ll spare you the details (available on Wikipedia). But I can roughly outline the idea behind the method.
The Lucas-Lehmer primality test is based on the research of Galois, who investigated symmetries in various mathematical objects at the beginning of the 19th century. Unlike his predecessors, however, he did not limit himself to geometric figures but also considered the symmetries of equations or number fields. The latter term describes a set of numbers in which all four basic arithmetic operations (that is, addition, subtraction, multiplication and division) can be applied without leaving the set. In other words, if I add or divide two numbers from the set, I get a number that is also part of the set. Examples of number sets are the rational numbers (which include integers and fractions) or the real numbers.
But it turns out that there are smaller number sets containing only a finite number of integers from 0 to p – 1. To preserve the properties of a set, the numbers must be continued periodically; after p – 1, 0 follows again: (0, 1, 2, 3, …, p – 1, 0, 1, 2, …). Such so-called finite fields may seem strange, but in fact, we encounter them in daily life: on an analog clock, it is perfectly natural that 1 follows 12.
As it turns out, finite number systems are a field if and only if p is a prime number. And Galois discovered that these finite number fields possess special symmetric properties. Lucas exploited this principle in developing his primality test: If 2127 – 1 is a prime number, then the corresponding number field 0, 1, 2,…, 2127 – 2 must possess certain symmetrical properties. To generate this finite number system, you must divide all values greater than 2127 – 1 by 2127 – 1 and calculate the remainder. This is the final step in Lucas’s algorithm.
This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.
