On October 12, 2024, Luke Durant, a 36-year-old researcher from San Jose, California, and a former NVIDIA employee, confirmed the largest prime number known today: 2 to the power 136,279,841, minus 1. Written out in full, it has 41,024,320 digits. To find it, he ran thousands of server GPUs rented in data centers across 17 countries. And yet we have known for more than two thousand years that even bigger primes exist: Euclid proved it in a few lines, with no computer at all.
Prime numbers are one of the oldest objects in mathematics and one of the most useful today. They sit at the heart of RSA, an encryption system invented in 1977 and still in use. Here is what primes are, why they never run out, and how they keep a secret.
What is a prime number?
A prime number is a whole number with exactly two factors: 1 and itself. 2, 3, 5, 7, 11 and 13 are prime; 12 is not, since it is divisible by 2, 3, 4 and 6. Numbers greater than 1 that are not prime are called composite.
The number 1 is not prime: it has only one factor. That choice has a reason. Every whole number greater than or equal to 2 can be written as a product of primes in exactly one way, up to the order of the factors: 360 = 2³ × 3² × 5, and nothing else. If 1 counted as prime, you could write 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3, and that uniqueness would disappear. Primes are the building blocks of multiplication, which is why they show up with factors and multiples in 6th grade math.
The sieve of Eratosthenes: finding primes by hand
The simplest way to list primes is credited to Eratosthenes of Cyrene (276 to 194 BC), who ran the great library of Alexandria. To find every prime up to 100:
- Write down all the whole numbers from 2 to 100.
- 2 is prime. Cross out all its multiples: 4, 6, 8, 10, and so on.
- The first number not crossed out, 3, is prime. Cross out its multiples: 9, 15, 21… (6, 12 and 18 are already gone).
- Repeat with 5, then with 7.
- Stop there: the next prime is 11, and 11 × 11 = 121 is bigger than 100. Every composite number up to 100 has a prime factor of 10 or less, so it is already crossed out.
What remains are the 25 primes below 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. The sieve still works well: it is what we used to recount, for this article, the 5,761,455 primes below one hundred million.
Euclid's proof: the primes never run out
In Book IX of the Elements, Proposition 20, Euclid states it this way, in the English version edited by David Joyce: "Prime numbers are more than any assigned multitude of prime numbers." In other words, no finite list contains them all. Here is the argument in modern language.
- Take any finite list of primes, for example 2, 3 and 5.
- Multiply them: N = 2 × 3 × 5 = 30. Every number on the list divides N.
- Add 1: N + 1 = 31.
- N + 1 is greater than 1, so it has at least one prime factor. Its smallest factor greater than 1 works: if that factor were not prime, it would have a smaller factor of its own, which would also divide N + 1.
- That prime factor cannot be on the list. If it divided both N and N + 1, it would divide their difference, which is 1. That is impossible.
- So we have found a prime that was not on the list. Since the list was arbitrary, no finite list is ever complete.
This proof is often presented as a proof by contradiction that starts from "the list of all primes." Euclid's own text is more direct: starting from three given primes, he builds a number that is either a new prime or divisible by a new prime. The only step by contradiction is the one showing that this factor is not on the list.
The classic mistake: "the product plus one is always prime"
If you try the proof with the first few primes, you hit a tempting pattern:
- 2 + 1 = 3, prime
- 2 × 3 + 1 = 7, prime
- 2 × 3 × 5 + 1 = 31, prime
- 2 × 3 × 5 × 7 + 1 = 211, prime
- 2 × 3 × 5 × 7 × 11 + 1 = 2,311, prime
It is easy to conclude that this number is always prime. It is not. At the next step, 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30,031 = 59 × 509. None of 2, 3, 5, 7, 11 or 13 divides 30,031 (the remainder is 1 every time), yet 30,031 is not prime: its prime factors, 59 and 509, are simply missing from the list. That is exactly what the proof guarantees. The step after that gives 510,511 = 19 × 97 × 277.
One more subtlety: the "new" prime does not have to be bigger than the ones on the list. Start from the list 3 and 5, and you get 3 × 5 + 1 = 16 = 2⁴: the missing prime is 2.
How the primes are spread out
Rarer and rarer
There are 25 primes up to 100, 168 up to 1,000, 78,498 up to one million and 5,761,455 up to one hundred million. Their share keeps shrinking (25%, then 7.8%, then 5.8%), but slowly and very regularly.
The prime number theorem describes that regularity: the number of primes up to x is roughly x ÷ ln x, where ln is the natural logarithm, the inverse of the exponential function you meet in Algebra 2. Legendre and Gauss conjectured it, and Jacques Hadamard and Charles-Jean de la Vallée Poussin proved it in 1896. For one million, the formula gives 72,382 against 78,498 in reality: the relative gap, still close to 8%, shrinks very slowly as x grows.
Around a number x, the average gap between consecutive primes is therefore about ln x: between 900,000 and 1,000,000 it is 13.8, and ln(1,000,000) ≈ 13.8.
Deserts as long as you like
You can even build stretches with no primes at all, as long as you want. Take 10! = 1 × 2 × 3 × … × 10 = 3,628,800. Then 10! + 2 is divisible by 2, 10! + 3 by 3, and so on up to 10! + 10, divisible by 10: nine composite numbers in a row. With 101! + 2 through 101! + 101, you get a hundred. Below one million, the longest gap runs from 492,113 to 492,227: 113 composite numbers in a row.
Twin primes, an open problem
At the other extreme, some primes are only 2 apart: 3 and 5, 11 and 13, 17 and 19, 29 and 31… There are 8,169 such pairs below one million. The twin prime conjecture says there are infinitely many. Nobody knows how to prove it.
In 2013, Yitang Zhang proved that there are infinitely many pairs of primes at most 70 million apart. An online collaboration, the Polymath project, then brought that bound down to 246, building in particular on a method by James Maynard. Getting from 246 to 2 is still open.
The largest known prime
As of October 25, 2026, the record still belongs to Luke Durant: 2 to the power 136,279,841, minus 1, found through the GIMPS volunteer project and announced on October 21, 2024. The previous record, 2 to the power 82,589,933, minus 1, dated from December 2018. Printed at 3,000 characters per page, the new one would fill about 13,700 pages.
It is a Mersenne number, of the form 2 to the power p, minus 1: for these numbers, the Lucas-Lehmer test checks primality much faster than for an arbitrary number. The exponents of 8th grade math lead straight to these giants.
RSA: encryption with prime numbers
A padlock anyone can close
In 1977, at MIT, Ronald Rivest, Adi Shamir and Leonard Adleman described a "public-key" encryption method, published the following year. The idea is like handing out open padlocks: anyone can snap one shut on a message, but only the owner has the key. Remarkably, Clifford Cocks, a mathematician at GCHQ, the British intelligence agency, had found an equivalent system shortly after joining in 1973; his discovery stayed secret for 24 years.
A complete example with 11 and 17
With small numbers, you can check everything by hand. "mod 187" means the remainder when dividing by 187.
- Pick two secret primes: p = 11 and q = 17.
- Compute n = p × q = 187. This number is public.
- Compute φ = (p − 1) × (q − 1) = 10 × 16 = 160. This number stays secret.
- Choose the public exponent e = 7, which shares no factor with 160. The public key is the pair (187, 7).
- Find the secret exponent d such that e × d leaves a remainder of 1 when divided by 160: 7 × 23 = 161 = 160 + 1, so d = 23.
- Encrypt the message m = 42: c = 42⁷ mod 187. Reducing at each step, the successive powers of 42 mod 187 are 42, 81, 36, 16, 111, 174 and finally 15 (and indeed 42⁷ = 230,539,333,248 leaves a remainder of 15). The encrypted message is c = 15.
- Decrypt: compute 15²³ mod 187. Since 23 = 16 + 4 + 2 + 1, square 15 repeatedly: 15² ≡ 38, 15⁴ ≡ 135, 15⁸ ≡ 86, 15¹⁶ ≡ 103 (mod 187). Then 15 × 38 ≡ 9, 9 × 135 ≡ 93, 93 × 103 ≡ 42. You get back m = 42.
Why does it work? A theorem of Euler, which generalizes Fermat's little theorem, says that if m shares no factor with n, then m to the power φ leaves a remainder of 1 when divided by n. Since e × d = 1 + 160, raising to the power e and then to the power d amounts to multiplying m by m to the power 160, which is 1 mod 187.
Why factoring is so hard
All the security rests on an asymmetry. A spy who knows n = 187 and e = 7 only has to factor n: 187 = 11 × 17 takes a few tries, which gives φ = 160 and d = 23. But in a real key, n has hundreds of digits.
Multiplying two 309-digit numbers takes a computer a few millionths of a second. Undoing the multiplication is another story. Trying every prime up to the square root of a 617-digit n would mean testing about 10 to the power 305 primes; at a billion billion tries per second, that would take about 10 to the power 280 years, while the universe is less than 14 billion years old.
Mathematicians have found far better methods than trial division, which is why keys keep getting longer. In their paper, Rivest, Shamir and Adleman estimated that with the best method they knew, at one operation per microsecond, factoring a 200-digit number would take 3.8 billion years. On February 28, 2020, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored RSA-250, a 250-digit number, using the number field sieve and the free CADO-NFS software: about 2,700 core-years of computing.
Two caveats. First, nobody has proved that factoring is hard: we simply know no fast method on an ordinary computer. Second, a large enough quantum computer could factor quickly using Shor's algorithm. That is why, in a November 2024 draft, the US National Institute of Standards and Technology (NIST) proposed deprecating 2,048-bit RSA keys after 2030 and disallowing RSA altogether after 2035, in favor of quantum-resistant algorithms.
The takeaway
The primes never run out: from any finite list, Euclid's argument builds a new one. They thin out slowly according to a precise law, leave gaps as long as you like, and still hide mysteries, like the twin primes. And the ease of multiplying, set against the difficulty of factoring, is enough to build an encryption system you can run by hand with 11 and 17.
In Mathflow, every skill comes in three levels: Explore, to play with the concepts and build intuition; Explain, to put your intuitions into words and uncover hidden mistakes; and Solve, to reason it out on your own. If you get stuck, Alphi, the AI math tutor, gives you a hint rather than the answer. The app was built with Inria, is rated 4.8 on the App Store, and is free to start.
Sources
- David E. Joyce (Clark University), Euclid's Elements, Book IX, Proposition 20, 1998
- John J. O'Connor and Edmund F. Robertson (MacTutor, University of St Andrews), Prime numbers, 2018
- GIMPS, GIMPS Discovers Largest Known Prime Number: 2^136,279,841-1, 2024
- D. H. J. Polymath, The "bounded gaps between primes" Polymath project: a retrospective, 2014
- Ronald Rivest, Adi Shamir and Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, 1978
- University of Bristol, Dr Clifford Cocks CB, 2008
- Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann, Factorization of RSA-250, 2020
- NIST, Transition to Post-Quantum Cryptography Standards (NIST IR 8547, initial public draft), 2024
