Is the number 170,141,183,460,469,231,731,687,303,715,884,105,727 a prime number? Before you ask the Internet for an answer, can you think about how you might answer this 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 a prime number. How did he do it? Lucas, who, by the way, also developed an entertaining game Tower of Hanoideveloped a method that is still useful today, more than a century later.
People have been fascinated by prime numbers for thousands of years. These numbers are only divisible by 1 and themselves, whereas any 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 keep many secrets. They appear on the number line with a certain regularity, but their appearance is characterized by fluctuations that are not yet quantifiable. This unpredictability has become a source of consternation for experts.
About supporting science journalism
If you enjoyed this article, please consider supporting our award-winning journalism. subscription. By purchasing a subscription, you help ensure a future of influential stories about the discoveries and ideas shaping our world today.
And math enthusiasts are constantly looking for new prime numbers. Current record (as of October 2025) for largest prime number is 2136 279 841 − 1, a number of 41,024,320 digits. Simply reading this number out loud will take approximately 240 days.
Prime numbers with special structure
Anyone who has observed the record prime numbers of recent years may have noticed that they have basically a similar structure: 2n – 1 (where n is a prime number). Prime numbers of this kind are called Mersenne prime numbers. And the number to which Lucas devoted almost two decades of his life is also a Mersenne prime, namely 2127 – 1. But there is a trick with these Mersenne primes: not every 2n– 1 – prime number for each prime value p. For example, 211 – 1 gives 2047 and can be written as the product of 23 and 89.
So, in the mid-19th century, Lucas asked himself whether it was possible127 – 1 was simple or not. He faced a huge challenge. The number is huge, consisting of 39 digits, and Lucas clearly did not have access to a computer at the time. He had to manually make sure that 2127 – 1 had no divisors (except 1 and itself).
One way to achieve this is to iterate over all 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 simply not feasible unless you know all the smaller prime numbers.
Lucas-Lehmer test for prime numbers
Lucas didn't give up. He developed a new method based on the discoveries of his colleague Evariste Galois, which required significantly less calculations.
Before we delve into the beautiful but admittedly abstract mathematics of Galois and Lucas, I will present Lucas' result, now known as the Lucas-Lemaire primality test.
To check if there are 2n – 1 is a prime number, Lucas developed the following algorithm:
-
Create a sequence of numbers whose first term is equal to With0 = 4 and where is each subsequent Withn calculated as With2n – 1 – 2. Therefore, the sequence is as follows: 4, 14, 194, 37,634 and so on.
-
Then 2n – 1 is a prime number if and only if n – 2nd member of the sequence (i.e. Withn – 2) is divisible by 2n – 1 without remainder. That is, every Mersenne prime number has this property, and vice versa, every Mersenne prime number has this property. Withn – 2 defines the Mersenne prime number 2n – 1.
So instead of dividing the Mersenne number by all prime numbers less than 2,127 – 1, it is enough to carry out calculations to determine With125 and then divide by 2127 – 1. This is much simpler, isn’t it?
In practice, there is only one tiny, or rather, very big problem. Sequence members Withn grow extremely quickly – so quickly that working with them is not particularly practical. Therefore, experts resort to a trick: they divide the members of the sequence Withn by the Mersenne number and continue to calculate the remainder if the division does not result in a whole number. This does not change the second part of the algorithm, so the condition for Mersenne primes remains the same: they must be able to divide into portions Withn – 2. This trick does Withn – 2 however, significantly less.
To better understand the simplicity criterion, we can understand it with a simple example: the Mersenne number 2⁵ – 1, equal to 31. Using the algorithm developed by Lucas, we need to calculate With3which is 37,634. Dividing this number by 31 gives the exact result 1214. This means that With3 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. Thus, he was able to show that it is indeed a prime number. To this day, it is the largest prime number found without the help of a computer.
However, Lucas did not conclusively prove that his method reliably identifies Mersenne primes. Only mathematician Derrick Henry Lemaire achieved this in 1930, which is why the method is known as the Lucas-Lemaire primality test.
Finite sets of numbers
But why does this strategy even work? In fact, the proof is quite technical, so I will spare you the details (available). on Wikipedia). But I can roughly outline the idea of the method.
The Lucas-Lemaire test for primality is based on the work of Galois, who in the early 19th century explored symmetries in various mathematical objects. However, unlike his predecessors, he did not limit himself to geometric figures, but also considered symmetries of equations or number fields. The latter term describes a set of numbers to 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 a set, I will get a number that is also part of the set. Examples of sets of numbers are rational numbers (which include whole and fractional numbers) or real numbers.
But it turns out that there are smaller sets of numbers containing only a finite number of integers from 0 to n – 1. To preserve the properties of a set, numbers must be continued periodically; after n – again follows 1, 0: (0, 1, 2, 3, …, n – 1, 0, 1, 2, …). These so-called trailing fields may seem strange, but in fact we encounter them in everyday life: on an analog clock, it is completely natural for 1 to follow 12.
As it turns out, systems of finite numbers are a field if and only if n is a prime number. And Galois discovered that these finite number fields have special symmetric properties. Lucas used this principle when developing his primality test: if 2127 – 1 is a prime number, then the corresponding numeric field is 0, 1, 2,…, 2127 – 2 must have certain symmetrical properties. To create this finite number system, you must divide all values greater than 2127 – 1 to 2127 – 1 and calculate the remainder. This is the last step of the Lucas algorithm.
This article originally appeared in spectrum of science and was reproduced with permission.
