8.3: Prime Mysteries

Some of the greatest mysteries and insights in number theory concern properties of prime numbers:

Definition \(\PageIndex{1}\)

A prime is a number greater than 1 that is divisible only by itself and 1. A number other than 0, 1, and -1 that is not a prime is called composite.⁵

Here are three famous mysteries:

Twin Prime Conjecture There are infinitely many primes \(p\) such that \(p + 2\) is also a prime.

In 1966, Chen showed that there are infinitely many primes \(p\) such that \(p + 2\) is the product of at most two primes. So the conjecture is known to be almost true!

Conjectured Inefficiency of Factoring Given the product of two large primes \(n = pq\), there is no efficient procedure to recover the primes \(p\) and \(q\). That is, no polynomial time procedure (see Section 3.5) is guaranteed to find \(p\) and \(q\) in a number of steps bounded by a polynomial in the length of the binary representation of \(n\) (not \(n\) itself). The length of the binary representation at most \(1 + \text{log}_2 n\).

The best algorithm known is the “number field sieve,” which runs in time proportional to:

\[\nonumber e^{1.9(\ln n)^{1/3}(\ln \ln n)^{2/3}}.\]

This number grows more rapidly than any polynomial in \(\text{log }n\) and is infeasible when \(n\) has 300 digits or more.

Efficient factoring is a mystery of particular importance in computer science, as we’ll explain later in this chapter.

Goldbach’s Conjecture We’ve already mentioned Goldbach’s Conjecture 1.1.8 several times: every even integer greater than two is equal to the sum of two primes. For example, \(4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5\), etc.

In 1939, Schnirelman proved that every even number can be written as the sum of not more than 300,000 primes, which was a start. Today, we know that every even number is the sum of at most 6 primes.

Primes show up erratically in the sequence of integers. In fact, their distribution seems almost random:

\[\nonumber 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, \ldots\]

One of the great insights about primes is that their density among the integers has a precise limit. Namely, let \(\pi (n)\) denote the number of primes up to \(n\):

Definition \(\PageIndex{2}\)

\[\nonumber \pi(n) ::= |\{p \in [2..n] \mid p \text{ is prime}\}|.\]

For example, \(\pi(1) = 0, \pi(2) = 1\), and \(\pi(10) = 4\) because 2, 3, 5, and 7 are the primes less than or equal to 10. Step by step, \(\pi\) grows erratically according to the erratic spacing between successive primes, but its overall growth rate is known to smooth out to be the same as the growth of the function \(n / \ln n\):

Theorem \(\PageIndex{3}\)

(Prime Number Theorem).

\[\nonumber \lim _{n \rightarrow \infty} \dfrac{\pi(n)}{n / \ln n}=1\]

Thus, primes gradually taper off. As a rule of thumb, about 1 integer out of every \(\ln n\) in the vicinity of \(n\) is a prime.

The Prime Number Theorem was conjectured by Legendre in 1798 and proved a century later by de la Vallée Poussin and Hadamard in 1896. However, after his death, a notebook of Gauss was found to contain the same conjecture, which he apparently made in 1791 at age 15. (You have to feel sorry for all the otherwise “great” mathematicians who had the misfortune of being contemporaries of Gauss.)

A proof of the Prime Number Theorem is beyond the scope of this text, but there is a manageable proof (see Problem 8.22) of a related result that is sufficient for our applications:

Theorem \(\PageIndex{4}\)

(Chebyshev’s Theorem on Prime Density). For \(n>1\),

\[\nonumber \pi (n) > \dfrac{n}{3 \ln n}.\]

A Prime for Google

In late 2004 a billboard appeared in various locations around the country:

\[\nonumber \left\{\begin{array}{l}
\text { first } 10 \text { -digit prime found } \\
\text { in consecutive digits of } e
\end{array}\right\} \cdot \text { com }\]

Substituting the correct number for the expression in curly-braces produced the URL for a Google employment page. The idea was that Google was interested in hiring the sort of people that could and would solve such a problem.

How hard is this problem? Would you have to look through thousands or millions or billions of digits of \(e\) to find a 10-digit prime? The rule of thumb derived from the Prime Number Theorem says that among 10-digit numbers, about 1 in

\[\nonumber \ln 10^{10} \approx 23\]

is prime. This suggests that the problem isn’t really so hard! Sure enough, the first 10-digit prime in consecutive digits of \(e\) appears quite early:

\(e = 2.718281828459045235360287471352662497757247093699959574966\)

\(96762772407663035354759457138217852516642 \color{blue}7427466391 \color{black}9320030\)

\(599218174135966290435729003342952605956307381323286279434 \ldots \)

 

⁵So 0, 1, and -1 are the only integers that are neither prime nor composite.