(C. F. Gauss 1777 – 1855)
Let us begin with a few facts about the prime numbers.
There are an infinite number of prime numbers. Remember we saw a proof of this by Euclid.
Every positive integer can be factored (uniquely) into a product of prime numbers. Here are some examples
100 = 2² x 5²
1001 = 7 x 11 x 13
10782625 = 5³ x 7 x 12323
5601319004198125000 = 2³ x 5^7 x 13^5 x 17^6
Euler’s theorem: If you have had some calculus before you can prove that 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 +…. = ∞. Euler showed that 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + 1/17+… (the sum of the reciprocals of the primes) is also equal to ∞.
Mersenne primes: Numbers of the form M_p = 2^p – 1 are called Mersenne numbers. Not all of them are prime. However, if M_p is prime then p must be prime. The converse is not true. Can you find a counterexample? However, Mersenne primes are good candidates for large prime numbers. For example, 2^(43112609) – 1 is prime (and has 12978189 digits). Mersenne primes even have their own homepage. In fact, when you click on that page, you can participate in the great Mersenne prime search (GIMPS). More often than not, when you hear in the popular press that mathematicians have discovered a new largest prime, it is usually a Mersenne prime.
Fermat primes: Numbers of the form F_n = 2^(2^n) + 1 are called Fermat numbers. Notice that
F_0 = 3
F_1 = 5
F_2 = 17
F_3 = 257
F_4 = 65537
and these numbers are prime! However, not every Fermat number is prime. For example
F_5 = 4294967297 = 641 x 6700417
F_6 = 18446744073709551617 = 274177 x 67280421310721
One can prove that if F^k + 1 is prime then k = 2^n.
Open question: Are F_0, F_1, F_2. F_3. F_4 the only Fermat primes? If you are thinking of getting out your computer and checking to see if F_7, F_8, F_9, etc are prime, don’t bother. As far as any computer can compute, these numbers are all not prime. But you never know, there might be some very very very large n out there such that F_n is a new Fermat prime. If you discover, such an n, you will definitely be famous.
Open question: Are there an infinite number of Fermat primes? Answer this question and you will be really really famous.
Why are the Fermat primes important? Well, they bring us back to straightedge and compass constructions we talked about earlier.
Theorem (Gauss, Wantzel): A regular n-gon is constructible using only a straightedge and compass if and only if n = 2^k (p_1 p_2….p_s), where p_1, p_2,…are distinct Fermat primes.
For example: A regular 17-gon is constructible (since 17 is a Fermat prime) as is a regular 34-gon (since 34 = 2 x 17). However a regular 18-gon is not constructible.
So, those are a few facts about primes. There are many many interesting others. The focus here is the prime number theorem. A question that has been around for many years is “How many primes are less than or equal to x?”. Let us denote π(x) to be the number of primes less than or equal to x.
π(2) = 1 (since 2 is the only prime less than or equal to 2)
π(3) = 2 (since both 2 and 3 are primes less than or equal to 2)
π(5) = 3
π(10) = 4
π(100) = 25
π(1000) = 168
π(1000000) = 78498
π(10000000000) = 455052511
Here is a plot of the first several values of π(x)
Notice how the graph is constant and jumps up when you reach a new prime number (Why?)
There is no precise formula for π(x). We can only understand it through its behavior as x goes to infinity. Gauss made large tables of π(x) and had the idea to compare it to x/ln(x), where ln(x) is the natural log function. Here are some graphs of π(x) and x/ln(x) on the same axis.
From looking at these graphs, one might conjecture, as Gauss did, that π(x)/(x ln(x)) goes to one as x goes to infinity. Here are a few graphs of π(x)/(x ln(x))
So it certainly seems like π(x)/(x ln(x)) goes to one as x goes to infinity. Maybe it is better to say π(x) ~ x/ln(x).
Theorem (The prime number theorem): π(x) ~ x/log(x)
This theorem took a long time to prove and was done in several steps which are too technical to get into here. The final result was proved independently by J. Hadamard and C. de la Valle Poussin in 1896. Their proofs were long but fortunately others after them were able to come up with shorter proofs.
A little more history here. Actually, Gauss used the Li(x) function which is the integral from 2 to x of 1/ln(x) as an estimator of x/ln(x).
In this case the prime number theorem becomes
pi(x) ~ Li(x) ~ x/Log(x).
Various mathematicians came up with estimates towards the prime number theorem. A nice link for this is from the Wolfram page.
Here is a nice consequence of the prime number theorem.
Corollary: If p_n in the n-th prime number, then p_n ~ n ln(n), i.e., p_n/(n ln(n)) goes to one as n goes to infinity.
We will give a proof of this in class. Let’s try this out. Here is a graph of p_n/(n ln(n))
Notice how this graph approaches one as n gets bigger and bigger.
G. H. Hardy (we will read about his life later) was able to improve this estimate.
Theorem (Hardy): p_n ~ n ln(n) + n ln(ln(n)) – n
Here is a graph of p_n/(n ln(n) + n ln(ln(n)) – n) below. Notice how this graph approaches one faster than the previous graph.
Final comment about the prime number theorem:
You will notice that the graph of li(x) lies on top of π(x). In other words li(x) > π – at least for the values we can see (in this case up to x equal to one million). We know that π(x) ~ x/ln(x) so these graphs get closer and closer but do we always have li(x) > π(x)? The answer is no. What is amazing is that the graphs of π(x) and li(x) do indeed switch places infinitely often but only after some really BIG number called Skewes number.
We can’t leave our study of the prime number theorem without mentioning that there is a closely related problem which poses to get a finer estimate on π(x). It is called the Riemann Hypothesis and is considered one of the most difficult and important unsolved problems in mathematics. In fact, it is so important to solve that the Clay Mathematics Institute has put up the money for a one million dollar prize for the person who can solve this problem. We won’t get into an explanation of the Riemann hypothesis now since it is a bit technical for an introductory course. But as you learn more mathematics, do look this problem up. It is definitely important and related to a lot of different types of mathematics. In fact many things are logically equivalent to the Riemann Hypothesis. So solve the Riemann Hypothesis and you solve a bunch of other problems too!