Is 170,141,183,460,469,231,731,687,303,715,884,105,727 prime? Before you seek answers from the Internet, might you consider how you might answer that question Without A computer or a digital calculator?
In the 1800s French mathematician Edouard Lucas spent years proving that this 39-digit number was in fact prime. how did he do it? Lucas, who also designed the entertaining game Tower of Hanoi, developed a method that is 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, while every other integer can be uniquely expressed as a product of multiple primes; For example, 15 = 3 × 5. Prime numbers essentially make up the periodic table of mathematics. They also keep many secrets. They appear on the number line with a certain regularity, but their occurrence is characterized by fluctuations that cannot yet be determined. This unpredictability has been a cause of panic for experts.
On supporting science journalism
If you enjoyed this article, consider supporting our award-winning journalism Subscribing By purchasing a subscription, you are helping ensure a future of impactful stories about the discoveries and ideas shaping our world today.
And mathematics enthusiasts are constantly on the lookout for new prime numbers. The current record for the largest prime (as of October 2025) is 2.136,279,841 – 1, a number consisting of 41,024,320 digits. Just reading this number out loud would take approximately 240 days.
Prime numbers with a special structure
Anyone who has observed the record-breaking prime numbers of recent years will have noticed that they mostly have a similar structure: 2.P – 1 (where P is a prime number). Prime numbers of this form are called Mersenne prime numbers. And the number to which Lucas devoted almost two decades of his life is also a Mersenne prime, namely 2.127 – 1. But there is some complication with these Mersenne primes: not every 2P– For every prime value 1 is a prime number. P. For example, 211 – 1 gives 2,047 and can be written as the product of 23 and 89.
So in the middle of the 19th century Lucas wondered whether 2127 – 1 was prime or not. He faced a formidable challenge. This number is huge, containing 39 digits, and Lucas apparently did not have access to a computer at the time. He had to manually ensure that 2127 – 1 had no divisors (except 1 and itself).
One way to accomplish this feat is to study all the prime numbers up to 2.127 – 1 and make sure it is not divisible by any of them. But this is extremely time consuming and impossible if you do not know all the smallest prime numbers.
Lucas–Lehmer prime number test
Lucas did not give up. He developed a new method based on the findings of his colleague Evarist Galois that required significantly less calculations.
Before we delve into the beautiful—but certainly abstract—mathematics of Galois and Lucas, I will present Lucas’s result, now known as the Lucas–Lehmer primality test.
To check that 2P – 1 is prime, Lucas developed the following algorithm:
-
Create a sequence of numbers whose first term is S0 = 4 and where each next Sn is calculated as S2n – 1 – 2. Therefore the sequence is: 4, 14, 194, 37,634, etc.
-
then 2P – 1 is a prime number if and only if P – second term of the sequence (i.e., SP – 2) is divisible by 2P – 1 without any remainder. That is to say, every Mersenne prime has this property, and conversely, every SP – 2 Mersenne defines prime 2P – 1.
So instead of dividing the Mersenne number by all primes less than 2127 – 1, it is enough to calculate to determine S125 and then divide by 2127 – 1. It’s very simple, isn’t it?
In practice, there is only one small—or rather very big—problem. Sequence Terms Sn Grow very quickly – so quickly, in fact, that working with them isn’t particularly practical. Therefore, experts resort to a trick: they split sequential words. Sn By Mersenne number and if the division does not result in a whole number then continue with the remainder. This does not change the other part of the algorithm, so the condition remains the same for Mersenne primes: they must be able to be divided evenly. SP – 2This does the trick SP – 2 However, quite small.
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 S3Which 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 hence, the latter is a prime number.
After years of hard work, Lucas developed this early test and applied it to 2127 – 1. Thus he was able to show that it was indeed a prime number. To date, it remains the largest prime number found without the aid of computers.
However, Lucas did not prove conclusively that his method reliably identified the Mersenne prime. This was only achieved by the mathematician Derrick Henry Lehmer in 1930, which is why the method is known as the Lucas–Lehmer primality test.
finite number set
But why does this strategy work at all? In fact, the proof is quite technical – and so, I will tell you the details (available on Wikipedia). But I can broadly outline the idea behind this method.
The Lucas–Lehmer primality test is based on the research of Galois, who investigated isomorphisms in various mathematical objects in the early 19th century. However, unlike his predecessors, he did not limit himself to geometric figures, but also considered equations or symmetries of number fields. The latter term describes a set of numbers to which all four basic arithmetic operations (i.e., 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 small number sets that contain only a finite number of integers ranging from 0 to P – 1. To preserve the properties of a set, the numbers must be continued from period to period; after P – 1, 0 again follows: (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 completely natural that 1 comes after 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 of fields have special symmetric properties. Lucas used this principle in developing his primality test: If 2127 – 1 is a prime number, then the corresponding number region is 0, 1, 2,…, 2127 – 2 must have some symmetric properties. To generate this finite number system, you must divide all values greater than 2 by127 – 1 by 2127 – 1 and calculate the remainder. This is the final step of Lucas’s algorithm.
This article was originally published in spectrum der wissenschaft And was reproduced with permission.