Primes in the wild: cicadas, codes and unsolved puzzles

You now know what primes are, how to find them, and why they behave as they do. This layer takes them out into the world and to the edge of what anyone knows.

You will see why insects may have evolved prime life cycles, how enormous primes protect the payments you make on a phone, how volunteers with home computers hunt record-breaking primes, and which simple-sounding questions about primes have defeated the greatest mathematicians for centuries. There are olympiad-style puzzles to crack and projects to try. Pick what interests you: this layer is a buffet, not a set menu.

Periodical cicadas of North America spend almost their whole lives underground as nymphs, feeding on sap from tree roots. Then, in one spring, millions crawl out at once, climb trees, sing, mate, lay eggs and die within a few weeks. Some broods do this every 13 years, others every 17 years.

Why primes? One leading idea is about predators. Suppose a predator population booms every few years. A cicada that emerges every 12 years would meet predators on 2-, 3-, 4- and 6-year cycles at every single emergence, because 2, 3, 4 and 6 are all factors of 12. A 13-year cicada shares no factor with any of these, so it lines up with each predator's boom far less often. The table shows how many years pass between meetings (the lowest common multiple of the two cycles).

Every time someone pays with a UPI app, logs in to net banking or buys something online, their phone and the bank's computer must agree on secret keys over the open internet, where anyone might be listening. The mathematics that makes this possible is called public-key cryptography, and one of its most famous forms rests on prime numbers.

The key idea is a one-way street:

• Multiplying two primes is easy. A computer multiplies two 300-digit primes in a tiny fraction of a second. Even by hand, 101 × 103 = 10,403 takes a minute.
• Undoing it, factorising the product to find the two primes, is extremely hard when the primes are huge. Given only 10,403, you have to search for a factor (you would need to try primes up to 101). For a product with 600 digits, no known method on today's computers finishes in any reasonable time.

Numbers of the form 2ⁿ − 1 (multiply 2 by itself n times, then subtract 1) are called Mersenne numbers, after the French friar Marin Mersenne, who studied them in the 1600s. When a Mersenne number is prime, it is a Mersenne prime: 3, 7, 31, 127, 8,191, …

Two facts guide the search:

• If n is composite, 2ⁿ − 1 is composite too. For example 2⁴ − 1 = 15 = 3 × 5 and 2⁶ − 1 = 63 = 7 × 9. So only prime n are worth testing.
• But a prime n is not enough: 2¹¹ − 1 = 2,047 = 23 × 89.

For Mersenne numbers there is a very fast special test, the Lucas–Lehmer test. That is why nearly every record prime of the last 70 years has been a Mersenne prime.

Add up the proper factors of 6 (all its factors except 6 itself): 1 + 2 + 3 = 6. The number equals the sum of its proper factors. The ancient Greeks called such numbers perfect. The next one is 28: 1 + 2 + 4 + 7 + 14 = 28. Then come 496 and 8,128, and then nothing until 33,550,336.

Numbers whose proper factors add up to more than the number, like 12 (1 + 2 + 3 + 4 + 6 = 16), are called abundant. Numbers whose proper factors add up to less, like 8 (1 + 2 + 4 = 7) and every prime (just 1), are called deficient.

The Mersenne link. Euclid proved that whenever 2ᵖ − 1 is prime, the number 2ᵖ⁻¹ × (2ᵖ − 1) is perfect:

• p = 2: 2 × 3 = 6
• p = 3: 4 × 7 = 28
• p = 5: 16 × 31 = 496
• p = 7: 64 × 127 = 8,128

About 2,000 years later, Euler proved that every even perfect number has this form. So each new Mersenne prime gives a new perfect number, and there are exactly as many even perfect numbers known as Mersenne primes.

In 1742 Christian Goldbach and Leonhard Euler exchanged letters about this idea:

Every even number greater than 2 is the sum of two primes.

4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 = 5 + 5, 12 = 5 + 7, … and 100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53.

Computers have checked every even number up to 4 × 10¹⁸ (four million million million). It is true every time. Yet nobody has proved it must be true for all even numbers. It is called Goldbach’s conjecture, and it is one of the most famous unsolved problems in mathematics.

A close cousin, the weak Goldbach conjecture (every odd number greater than 5 is the sum of three primes), was proved in 2013 by the Peruvian mathematician Harald Helfgott. Experts accept his proof, though the full written version is still being prepared for publication.

Recall the twin prime conjecture: there are infinitely many pairs of primes that differ by 2. It is at least 150 years old in its modern form and still unproved.

For a long time mathematicians could not even prove that there are infinitely many pairs of primes differing by any fixed amount, whether 2 or 1,000 or a billion. Then in 2013, Yitang Zhang, a little-known lecturer at the University of New Hampshire, proved that there are infinitely many pairs of primes that differ by less than 70 million. It was a stunning result from someone who had worked quietly on it for years.

Within months, James Maynard found a different method, and a large online collaboration called Polymath combined the ideas. The gap came down to 246. So we now know that infinitely many pairs of primes differ by 246 or less. Getting from 246 to 2 is the remaining challenge, and experts think it needs a genuinely new idea.

Meanwhile, the largest known twin primes, found in 2016, have 388,342 digits each.

Our numbers are written in base ten: each place is worth ten times the one to its right. Other bases are possible. Computers use base two (binary), and many old measuring systems used twelves and sixties.

Being prime does not depend on the base. Thirteen objects cannot be arranged in a rectangle, whether you write the number as 13 (base ten), 1101 (base two) or 11 (base twelve). Primality is about the quantity, not the way it is written.

Divisibility rules do depend on the base. The digit-sum test for 3 and 9 works because ten is one more than nine. In base twelve, the digit-sum test works for eleven (and its factors), because twelve is one more than eleven; and the last-digit test works for 2, 3, 4 and 6, because they all divide twelve. In binary, a number is even exactly when its last digit is 0, just as in base ten a number is a multiple of 10 when it ends in 0.

People who work with primes and factors today include:

• Cryptographers, who design and test the codes protecting banks, payment systems such as UPI, messaging apps and governments. India’s growing digital public infrastructure needs many of them.
• Cybersecurity analysts, who make sure those codes are used correctly, since most real attacks exploit mistakes rather than the mathematics.
• Number theorists at universities and research institutes such as the Indian Statistical Institute, the Tata Institute of Fundamental Research, the Chennai Mathematical Institute and the IITs.
• Software engineers, who use primes in hashing, random number generators and error-correcting codes that keep data safe on phones and satellites.
• Quantum computing researchers, racing to build machines that could factorise big numbers, and others racing to build codes those machines cannot break.