How Can Infinitely Many Primes Be Infinitely Far Apart?
Robert Neubecker for Quanta Magazine
Introduction
If you’ve been following the math news this month, you know that the 35-year-old number theorist James Maynard won a Fields Medal — the highest honor for a mathematician. Maynard likes math questions that “are simple enough to explain to a high school student but hard enough to stump mathematicians for centuries,” Quanta reported, and one of those simple questions is this: As you move out along the number line, must there always be prime numbers that are close together?
You may have noticed that mathematicians are obsessed with prime numbers. What draws them in? Maybe it’s the fact that prime numbers embody some of math’s most fundamental structures and mysteries. The primes map out the universe of multiplication by allowing us to classify and categorize every number with a unique factorization. But even though humans have been playing with primes since the dawn of multiplication, we still aren’t exactly sure where primes will pop up, how spread out they are, or how close they must be. As far as we know, prime numbers follow no simple pattern.
Our fascination with these fundamental objects has led to the invention, or discovery, of hundreds of different types of primes: Mersenne primes (primes of the form 2n − 1), balanced primes (primes that are the average of two neighboring primes), and Sophie Germain primes (a prime p such that 2p + 1 is also prime), to name a few.
Interest in these special primes grew out of playing around with numbers and discovering something new. That’s also true of “digitally delicate primes,” a recent addition to the list that has led to some surprising results about the most basic of questions: Just how rare or common can certain kinds of primes be?
To appreciate this question, let’s start with one of the first intriguing facts an aspiring number enthusiast learns: There are infinitely many prime numbers. Euclid proved this 2,000 years ago using one of the most famous proofs by contradiction in all of math history. He started by assuming that there are only finitely many primes and imagined all n of them in a list:
$latexp_1, \ p_2, \ p_3, \ …, \ p_n$.
Then he did something clever: He thought about the number $latexq=p_1 \times p_2 \times p_3 \times … \times p_n+1$.
Notice that q can’t be on the list of primes, because it’s bigger than everything on the list. So if a finite list of primes exists, this number q can’t be prime. But if q is not a prime, it must be divisible by something other than itself and 1. This, in turn, means that q must be divisible by some prime on the list, but because of the way q is constructed, dividing q by anything on the list leaves a remainder of 1. So apparently q is neither prime nor divisible by any prime, which is a contradiction that results from assuming that there are only finitely many primes. Therefore, to avoid this contradiction, there must in fact be infinitely many primes.
Given that there are infinitely many of them, you might think that primes of all kinds are easy to find, but one of the next things a prime number detective learns is how spread out the primes can be. A simple result about the spaces between consecutive prime numbers, called prime gaps, says something quite surprising.
Among the first 10 prime numbers — 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29 — you can see gaps that consist of one or more composite numbers (numbers that are not prime, like 4, 12 or 27). You can measure these gaps by counting the composite numbers in between: For example, there is a gap of size 0 between 2 and 3, a gap of size 1 between both 3 and 5 and 5 and 7, a gap of size 3 between 7 and 11, and so on. The largest prime gap on this list consists of the five composite numbers — 24, 25, 26, 27 and 28 — between 23 and 29.
Now for the incredible result: Prime gaps can be arbitrarily long. This means that there exist consecutive prime numbers as far apart as you can imagine. Perhaps just as incredible is how easy this fact is to prove.
We already have a prime gap of length 5 above. Could there be one of length 6? Instead of searching lists of primes in hopes of finding one, we’ll just build it ourselves. To do so we’ll use the factorial function used in basic counting formulas: By definition, $latexn!=n \times(n-1) \times (n-2) \times … \times 3 \times 2 \times 1$, so for example $latex3!=3 \times 2\times 1 = 6$ and $latex5!=5 \times 4 \times 3 \times 2 \times 1=120$.
Now let’s build our prime gap. Consider the following sequence of consecutive numbers:
$latex 7!+2$, $latex7!+3$, $latex 7!+4$, $latex7!+5$, $latex 7!+6$, $latex 7!+7$.
Since $latex7!=7 \times 6 \times 5 \times 4 \times 3 \times2 \times 1$, the first number in our sequence, $latex7!+2$, is divisible by 2, which you can see after a little bit of factoring:
$latex7!+2=7 \times 6 \times 5 \times 4 \times 3 \times2 \times 1+2$
$latex= 2(7 \times 6 \times 5 \times 4 \times 3 \times 1+1)$.
Likewise, the second number, $latex7!+3$, is divisible by 3, since
$latex7!+3=7 \times 6 \times 5 \times 4 \times 3 \times2 \times 1+3$
$latex= 3(7 \times 6 \times 5 \times 4 \times2 \times 1+1)$.
Similarly, 7! + 4 is divisible by 4, 7! + 5 by 5, 7! + 6 by 6, and 7! + 7 by 7, which makes 7! + 2, 7! + 3, 7! + 4, 7! + 5, 7! + 6, 7! + 7 a sequence of six consecutive composite numbers. We have a prime gap of at least 6.
This strategy is easy to generalize. The sequence
$latexn!+2$, $latexn!+3$, $latexn!+4$, $latex…$, $latexn!+n$.
is a sequence of $latexn-1$ consecutive composite numbers, which means that, for any n, there is a prime gap with a length of at least $latexn-1$. This shows that there are arbitrarily long prime gaps, and so out along the list of natural numbers there are places where the closest primes are 100, or 1,000, or even 1,000,000,000 numbers apart.
A classic tension can be seen in these results. There are infinitely many prime numbers, yet consecutive primes can also be infinitely far apart. What’s more, there are infinitely many consecutive primes that are close together. About 10 years ago the groundbreaking work of Yitang Zhang set off a race to close the gap and prove the twin primes conjecture, which asserts that there are infinitely many pairs of primes that differ by just 2. The twin primes conjecture is one of the most famous open questions in mathematics, and James Maynard has made his own significant contributions toward proving this elusive result.
This tension is also present in recent results about so-called digitally delicate primes. To get a sense of what these numbers are and where they may or may not be, take a moment to ponder the following strange question: Is there a two-digit prime number that always becomes composite with any change to its ones digit?
To get a feel for digital delicacy, let’s play around with the number 23. We know it’s a prime, but what happens if you change its ones digit? Well, 20, 22, 24, 26 and 28 are all even, and thus composite; 21 is divisible by 3, 25 is divisible by 5, and 27 is divisible by 9. So far, so good. But if you change the ones digit to a 9, you get 29, which is still a prime. So 23 is not the kind of prime we’re looking for.
What about 37? As we saw above, we don’t need to bother checking even numbers or numbers that end in 5, so we’ll just check 31, 33 and 39. Since 31 is also prime, 37 doesn’t work either.
Does such a number even exist? The answer is yes, but we have to go all the way up to 97 to find it: 97 is a prime, but 91 (divisible by 7), 93 (divisible by 3) and 99 (also divisible by 3) are all composite, along with the even numbers and 95.
A prime number is “delicate” if, when you change any one of its digits to anything else, it loses its “primeness” (or primality, to use the technical term). So far we see that 97 is delicate in the ones digit — since changing that digit always produces a composite number — but does 97 satisfy the full criteria of being digitally delicate? The answer is no, because if you change the tens digit to 1 you get 17, a prime. (Notice that 37, 47 and 67 are all primes as well.)
In fact, there is no two-digit digitally delicate prime. The following table of all the two-digit numbers, with the two-digit primes shaded in, shows why.
All the numbers in any given row have the same tens digit, and all the numbers in any given column have the same ones digit. The fact that 97 is the only shaded number in its row reflects the fact that it is delicate in the ones digit, but it’s not the only prime in its column, which means it is not delicate in the tens digit.
A digitally delicate two-digit prime would have to be the only prime in its row and column. As the table shows, no such two-digit prime exists. What about a digitally delicate three-digit prime? Here’s a similar table showing the layout of the three-digit primes between 100 and 199, with composite numbers omitted.
Here we see that 113 is in its own row, which means it’s delicate in the ones digit. But 113 isn’t in its own column, so some changes to the tens digit (like to 0 for 103 or to 6 for 163) produce primes. Since no number appears in both its own row and its own column, we quickly see there is no three-digit number that is guaranteed to be composite if you change its ones digit or its tens digit. This means there can be no three-digit digitally delicate prime. Notice that we didn’t even check the hundreds digit. To be truly digitally delicate, a three-digit number would have to avoid primes in three directions in a three-dimensional table.
Do digitally delicate primes even exist? As you go further out on the number line the primes tend to get sparser, which makes them less likely to cross paths in the rows and columns of these high-dimensional tables. But larger numbers have more digits, and each additional digit decreases the likelihood of a prime being digitally delicate.
If you keep going, you’ll discover that digitally delicate primes do exist. The smallest is 294,001. When you change one of its digits, the number you get — 794,001, say, or 284,001 — will be composite. And there are more: The next few are 505,447; 584,141; 604,171; 971,767; and 1,062,599. In fact, they don’t stop. The famous mathematician Paul Erdős proved that there are infinitely many digitally delicate primes. And that was just the first of many surprising results about these curious numbers.
For example, Erdős didn’t just prove that there are infinitely many digitally delicate primes: He proved that there are infinitely many digitally delicate primes in any base. So if you choose to represent your numbers in binary, ternary or hexadecimal, you’re still guaranteed to find infinitely many digitally delicate primes.
And digitally delicate primes aren’t just infinite: They comprise a nonzero percentage of all prime numbers. This means that if you look at the ratio of the number of digitally delicate primes to the number of primes overall, this fraction is some number greater than zero. In technical terms, a “positive proportion” of all primes are digitally delicate, as the Fields medalist Terence Tao proved in 2010. The primes themselves don’t make up a positive proportion of all numbers, since you’ll find fewer and fewer primes the farther out you go along the number line. Yet among those primes, you’ll continue to find digitally delicate primes often enough to keep the ratio of delicate primes to total primes above zero.
Maybe the most shocking discovery was a result from 2020 about a new variation of these strange numbers. By relaxing the concept of what a digit is, mathematicians reimagined the representation of a number: Instead of thinking about 97 by itself, they instead thought of it as having leading zeros:
…0000000097.
Each leading zero can be thought of as a digit, and the question of digital delicacy can be extended to these new representations. Could there exist “widely digitally delicate primes” — prime numbers that always become composite if you change any of the digits, including any of those leading zeros? Thanks to the work of the mathematicians Michael Filaseta and Jeremiah Southwick, we know that the answer, surprisingly, is yes. Not only do widely digitally delicate primes exist, but there are infinitely many of them.
Prime numbers form an infinite string of mathematical puzzles for professionals and enthusiasts to play with. We may never unravel all their mysteries, but you can count on mathematicians to continually discover, and invent, new kinds of primes to explore.
Exercises
1. What’s the biggest prime gap among the primes from 2 to 101?
2. To prove that there are infinitely many primes, Euclid assumes there are finitely many primes $latexp_1, \ p_2, \ p_3, \ …, \ p_n$, and then shows that $latexq=p_1 \times p_2 \times p_3 \times … \times p_n+1$ isn’t divisible by any prime on the list. Doesn’t this mean that q has to be prime?
3. A famous result in number theory is that there is always a prime between k and 2k (inclusive). This is hard to prove, but it’s easy to prove that there’s always a prime between k and $latexq=p_1 \times p_2 \times p_3 \times … \times p_n+1$ (inclusive), where $latexp_1, \ p_2, \ p_3, \ …, \ p_n$ are all the primes less than or equal to k. Prove it.
4. Can you find the smallest prime number that is digitally delicate in the ones and tens digits? This means that changing the ones or tens digit will always produce a composite number. (You might want to write a computer program to do this!)
Challenge Problem: Can you find the smallest prime number that is digitally delicate when represented in binary? Recall that in binary, or base 2, the only digits are 0 and 1, and each place value represents a power of 2. For example, 8 is represented as $latex1000_2$, since $latex 8=1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 0 \times 2^0$, and 7 in base 2 is $latex111_2$, since $latex7=1 \times2^2 + 1 \times 2^1 + 1 \times 2^0$.
Click for Answer 1:
Click for Answer 2:
Click for Answer 3:
Click for Answer 4:
Click for Answer to Challenge Problem:
