I’ve been traveling so this one is from the archives. Enjoy! – AB

What are primes?

A prime number is a positive integer with exactly two different divisors. For example, 2 is prime, as 1 and 2 divide it. The same is true for 3, 5, and 7. But 6 is not prime as it has four divisors 1, 2, 3 and 6.

On first glance, we may think that primes are not so useful. After all, we don’t use primes in daily life. Or do we? Read on!

First, we provide a few basic and not so basic facts about primes.

• A handy fact: to determine that a number n is prime, check for prime divisors at most √n. For example, we can quickly determine that 83 is prime by checking that 2, 3, 5 and 7 are not divisors.
• Every number is a product of primes. For example, 26 = 2• 13, and this is called a prime factorization. Prime factorizations are unique up to the order of the factors. This is one of the simplest reasons why primes matter: in a sense, they form an infinite periodic table of elements from which all other numbers are built. If you know a numbers prime factorization, then it tells you something fundamental about that number. Depending on the work you are doing, it may be better to represent 12,397 as 7 ² • 11 • 23.
• At the time of writing this blog, the largest prime that we know is 2^74,207,281 − 1, a number with over twenty two million digits. Of course, there are much larger primes. In fact, most primes are larger than this tiny number! As Euclid proved over two thousand years ago, there are infinitely many primes.
• If you look at how they are dispersed on the number line, then the primes are ubiquitous.  According to the Bertrand–Chebyshev theorem: if you take an integer n and double it to form 2n, then you know there is always a prime between n and 2n.
• Primes don’t seem to arise according to any fixed pattern that we know. However, long clumps of them do appear in certain kinds of patterns. An arithmetic progression is a sequence of integers of the form an+b. For example, 3, 5, and 7 appear as 2n+3, where n = 0, 1, and 2. A breakthrough result of Ben Green and Terrance Tao from 2004 showed that arbitrarily long, finite sequences of primes are contained in arithmetic progressions.
• There are fast algorithms to check if a number is prime. Agrawal, Kayal, and Saxena proved in 2002 that deciding if a number is prime or composite is in polynomial time. However, we don’t know the computational complexity of finding the prime factorization of an integer.

Primes also have beautiful density patterns as exhibited by the prime number theorem and the Ulam spiral. Check out this video on the density of primes.

Why are primes important to security?

Primes matter in real life. You can’t hide from the primes. Each time you use your bank card or do on-line shopping, primes are likely lurking in the background.

The science of encoding and transmitting secure data is called cryptography. Cryptography has an ancient past, but in the last century mathematicians developed sophisticated cryptographic algorithms that are very hard to crack.

Cryptography algorithms like RSA and others rely on so-called trapdoor functions; that is, functions easy to compute in one direction but not in the reverse. For example, prime factorization is a trap door: if I give you two primes, then it is easy to compute their product. However, if I give you a large number that is the product of two primes like 2⁹⁹⁷ -1, then it extremely tough to find the two primes.

Many other applications in computer science and engineering use primes. For example, random number generators and error correcting codes exploit properties of primes.

Why are primes interesting to mathematicians?

To put it bluntly, mathematicians don’t understand primes as well as would like.

Primes are the bread and butter of number theory, and in that field, there are many deep, unsolved problems them. One of the simplest to state of these is the Goldbach conjecture: each even integer greater than 2 is a sum of two primes. For example, 8 is 3+5, and 26 is 23+3.  The Goldbach conjecture has been open since the 18th century.

We don’t understand gaps between primes very well. The Twin Prime Conjecture states that there infinitely many primes p so that p+2 is also prime. In other words, we can find infinitely many examples of primes with gap 2.  In 2013, Yitang Zhang announced that he could prove there were infinitely many primes with gap less than 70 million. That gap may seem ridiculously large, but it was a major breakthrough. Using his techniques, Terrance Tao and others have reduced the gap down to 246.

Another deep unsolved problem connected to primes is the Riemann hypothesis, which is more technical to state. Define the Riemann zeta function (or just zeta function) at value s as the infinite series:

The zeta function can take complex values, and is defined if the real part of s is greater than 1; for example, at s=1 it is the divergent harmonic series. At s=2, it has value π²/6.

There are infinitely many zeroes (that is, solutions of the equation ζ(s)=0) of the zeta function, such as the negative even integers, and these are called trivial zeroes. The zeta function also has complex number zeroes. The Riemann hypothesis claims that the real part of any non-trivial zero of the zeta function is 1/2. In other words, all the non-trivial zeroes live on the critical line z = 1/2 in the complex plane.

While the Riemann hypothesis appears unrelated to primes on the surface, many conjectures about primes rely on its validity. One consequence has to do with the distribution of primes numbers. When I recently interviewed Barry Mazur (whose book on primes and the Riemann hypothesis came our recently; Barry is one of the leading number theorists), he gave his perspective on this connection.  We close with his words.

“Draw a graph (on one standard-size page) that charts the number of primes less than x, and where the range is for values of x between 1 and, say, 40, and it looks like the most randomly constructed staircase. And now draw one where the range is for values of x between 1 and, say, 100,000 primes and you get a strikingly smooth graph! Looking at primes from afar, their erratic turbulence disappears. That is the perplexity: from afar the graph of primes is so smooth, while from near it looks disorganized and complicated. The Riemann hypothesis continues the grand project begun by Gauss of explaining exactly how smooth that progression of primes is.”

Anthony Bonato