Prime Number Theorems (Infinitude of Primes)

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

We discuss prime numbers and how to find them using the sieve of Eratosthenes. Thereafter, we will then prove important prime number theorems including infinitude of prime numbers. Finally, we will show that every natural number has a prime divisor by assuming the well-ordering axiom.

The mathematical properties of prime numbers began to draw the interests of mathematicians from as early as Ancient Greece. Most of these ancient mathematicians attempted to find the largest prime number that can exist. However, it was until circa 300 BC that Euclid proved that no such thing as the largest prime number can possible exist.

Yet still, subsequent mathematicians dedicated their time to trying to find a formula by which one could establish an unending series of prime numbers. It is through this quest that the prime number theorem emerged.

Prime Number Theorems Today

Today, these theorems have extensive application in number theory, in which they not only give us the fundamental theory of arithmetic that is a cornerstone of the mathematics of integers, but also helps explain how the prime numbers are distributed asymptotically among the integers.

Among the facts that have come to be classified under the umbrella of prime number theorem includes the infinite nature of primes, the ability to factorize every positive integer into a product of primes, Euler’s Theorem on reciprocals of prime numbers, Mersenne primes, Fermat’s primes, among others.

One fundamental method that has proven quite efficient in the process of establishing prime numbers is the sieve of Eratosthenes, although its efficiency is limited to finding prime numbers that lie between one and ten million.

Primes and Composites

Several of the most basic and interesting questions concerning the integers involves the prime numbers. For example, are there infinitely many primes of the form $n^2+1$? This question is easy to understand, but no one has been able to answer it.

From a certain point of view, the prime numbers are the building blocks for the integers; that is to say, every integer greater than 1 has a prime factor. Indeed, every positive integer is a product of primes. This result was known to the ancient Greeks and is sometimes referred to as Euclid’s lemma.

One of the first questions that comes to mind concerning prime numbers is:

  • how many prime numbers are there?
  • why are primes so important to talk about?
  • without using trial division, how can one determine whether a given integer is prime or composite?
  • is it possible for given a function to find all the prime numbers?
  • are there arbitrarily long sequences of integers, all of which are not primes?

These simple questions have kept mathematicians busy for thousands of years.

Working with Primes

Definition. A prime number is a natural number greater than 1 that is divisible by no natural numbers other than 1 and itself. A natural number greater than 1 that is not prime is called a composite number.

By definition, a number greater than one is said to be prime if it only has two divisors, namely one and itself. A quick review of this series of numbers indicates that the higher one counts, the fewer the cases of prime numbers discovered, yet the process continues infinitely.

The difficulty in finding higher value prime numbers has been a persistent problem for Prime Number Theorem mathematicians across the globe, often with news always emerging on the discovery of new, higher value primes.

Note that these are always expressed as Mersenne primes. With mathematicians having agreed that Mersenne primes may not all be prime, the discussion shifts to the question of the possible number of prime numbers that exist out there.

Sieve of Eratosthenes

The idea, passing over 1, is to find a prime number and then cross out all of the multiples of this prime number. For example, 2 is prime but every even number is not and so cross all even numbers off the list. Next, 3 is prime and so cross out every multiple of three, because they are not prime. Continue in this fashion, and then the numbers left are the prime numbers. Of course for a given large integer, this is not practical, and particularly if your time is limited. Since the time of Eratosthenes, sophisticated versions of this algorithm (called the Sieve of Eratosthenes) have achieved new results.

\begin{equation} \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\ 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 \\ 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\ 51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 \\ 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70 \\ 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 \\ 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 & 90 \\ 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 \end{matrix} \end{equation}

Consider the first 5 rows in the above array. How many primes are there in the first 5 rows? How many in the last five rows? If one carries out the sieve of Eratosthenes between 10,000 and 10,050, you will find that there are just 4 prime numbers. Can we find 5 rows where there are no prime numbers? What is the last prime number?

Limits of the Sieve of Eratosthenes

As you may have noticed from the previous paragraph, the number of prime numbers tends to decrease as one counts higher. This means that it becomes increasingly difficult to manually employ the sieve of Eratosthenes as the value of interest increases.

While you may have noticed how difficult it is to find the four prime numbers that exist between 10,000 and 10,050, it is relatively easy to do so using an algorithm. Such algorithms employ the segmented sieve approach that works by dividing the range of interest into segments, each of size the square root of the range. The process, however, is equally time consuming.

Prime Number Theorem: Prime Divisors

The prime number theorem describes the distribution of prime numbers among the integers, and argues that for every integer $N$ that is large enough, there exists another integer less than $N$ that is prime. In others words, it is possible to factor any integer large enough as a product of its factors, with at least one of the factors being prime.

A prime divisor is therefore any prime number that divides N, where N is any integer greater than 1. Note that just as is the case with finding prime numbers, the process of finding these prime divisors grows increasingly complicated as the value of N increases. Add some text here.

The following lemma, while known to Euclid, is proven using the (modern) Well-Ordering Axiom.

Theorem. (Prime Divisor) Every natural number greater than 1 has a prime divisor.

Proof. Assume, for a contradiction, that there exists a natural number greater than 1 that does not have a prime divisor. Then since the set of all natural numbers greater than 1 without a prime divisor is nonempty, the Well-Ordering Axiom states that this set must have a least positive natural number, say $n,$ that does not have a prime divisor and is greater than 1. Since $n$ does not have a prime divisor and $n$ divides $n$, $n$ must not be prime. Thus, $n=a b$ and since $a<n,$ $a$ must have a prime divisor and similarly for $b.$ Therefore, $n=a b$ must have a prime divisor. This contradiction, leads us to the desired conclusion that every natural number greater than 1 must have a prime divisor.

Here are the prime numbers less than 1000.

\begin{equation} \begin{matrix} 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 \\ 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 \\ 73 & 79 & 83 & 89 & 97 & 101 & 103 & 107 & 109 & 113 \\ 127 & 131 & 137 & 139 & 149 & 151 & 157 & 163 & 167 & 173 \\ 179 & 181 & 191 & 193 & 197 & 199 & 211 & 223 & 227 & 229 \\ 233 & 239 & 241 & 251 & 257 & 263 & 269 & 271 & 277 & 281 \\ 283 & 293 & 307 & 311 & 313 & 317 & 331 & 337 & 347 & 349 \\ 353 & 359 & 367 & 373 & 379 & 383 & 389 & 397 & 401 & 409 \end{matrix} \end{equation}

\begin{equation} \begin{matrix} 419 & 421 & 431 & 433 & 439 & 443 & 449 & 457 & 461 & 463 \\ 467 & 479 & 487 & 491 & 499 & 503 & 509 & 521 & 523 & 541 \\ 547 & 557 & 563 & 569 & 571 & 577 & 587 & 593 & 599 & 601 \\ 607 & 613 & 617 & 619 & 631 & 641 & 643 & 647 & 653 & 659 \\ 661 & 673 & 677 & 683 & 691 & 701 & 709 & 719 & 727 & 733 \\ 739 & 743 & 751 & 757 & 761 & 769 & 773 & 787 & 797 & 809 \\ 811 & 821 & 823 & 827 & 829 & 839 & 853 & 857 & 859 & 863 \\ 877 & 881 & 883 & 887 & 907 & 911 & 919 & 929 & 937 & 941 \\ 947 & 953 & 967 & 971 & 977 & 983 & 991 & 997 & & \end{matrix} \end{equation}

Prime Number Theorem: Infinitude of Primes

The following proof of the infinitude of primes is a great example of what is called proof by contradiction. The idea is to suppose that there are finitely many prime numbers, and then use these primes to create another natural number whose prime divisor can not be in the original list of all prime numbers.

Theorem. (Euclid) There are infinitely many primes.

Proof. Assume that the prime numbers are listed in ascending order with $p_1=2,$ $p_2=3,$ $p_3=5,$ and so on; and assume (for a contradiction) that $p_k$ is the last prime. Consider the natural number, $$P=p_1p_2\cdots p_k+1.$$ Since every positive natural number greater than 1 has a prime divisor, $P$ has a prime divisor, say $p_m.$ However, $p_m$ can not divide $P$ since $P$ is of the form, $P=c p_m+1.$ Therefore $p_k$, the last prime number, cannot exist.

Exercises on Prime Number Theorems

Exercise. Determine which of the following integers are prime: 201, 207, 213, 203, 211, 221.

Exercise. Find the smallest prime in the arithmetic progression $a n+b$.

$(1) \quad a=3, b=1$,

$(2) \quad a=5, b=4$,

$(3) \quad a=7, b=12$,

$(4) \quad a=11, b=16.$

Exercise. Using the sieve of Eratosthenes, find the prime numbers less than 200.

Exercise. Show that $x^2-x+41$ is prime for all integers $x$ with $0\leq x\leq 40.$ Show that it is composite for $x=41.$

Exercise. Show that $2x^2+11$ is prime for all integers $x$ with $0\leq x\leq 10.$ Show that it is composite for $x=11.$

Exercise. Show that $2x^2+29$ is prime for all integers $x$ with $0\leq x\leq 28.$ Show that it is composite for $x=29.$

Exercise. It has been conjectured that there are infinitely many primes of the form $n^2-2.$ Exhibit five such examples.

Exercise. Show that any prime of the form $3n+1$ is also of the form $6m+1.$

Exercise. Show that each integer of the form $3n+2$ has a prime factor of this form.

Exercise. Show the only prime $p$ for which $3p+1$ is perfect square is $p=5.$

Exercise. Find all primes that are the difference of the fourth powers of two integers.

Exercise. Show that no integer of the form $n^3+1$ is a prime, other than $2.$

Exercise. Prove that all odd primes are either of the form $4n+1$ or $4n-1$ for some $n\in \mathbb{N}$.

Exercise. Prove that, if $n\in \mathbb{N}$ s a product of primes of the form $4m+1$, then $n$ must be of that form.

More Exercises on Prime Number Theorems

Exercise. Let $Q_n=p_1p_2\cdot \cdot \cdot p_n+1$ where $p_1,p_2,\cdots, p_n$ are the smallest primes. Determine the smallest prime factor of $Q_n$ for $n=1,2,3,4,5,$ and 6. Do you think that $ Q_n$ is prime infinitely often?

Exercise. Show there are infinitely many prime numbers of the form $4k+3$.

Exercise. Give an example to show that the following conjecture is not true: Every positive integer can be written in the form $p+a^2$, where $p$ is either a prime or 1, and $a\geq 0.$

Exercise. Another unproven conjecture is that there are an infinitude of primes that are 1 less than a power of 2, such as $3=2^2-1.$ Find four more of these primes.

Exercise. It has been conjectured that every even integer can be written as the difference of consecutive primes in finitely many ways. For example, $$6=29-23=137-131=599-593=1019-1013= \cdots $$ Express the integer 10 as the difference of two consecutive primes in 15 ways.

Exercise. Find four primes of the form $2^n+1$ for $n\in \mathbb{N}$.

Exercise. Prove that if $2^n+1$ is prime, then $n=0$ or $n=2k$ for some integer $k$.

Exercise. Prove that $p$ is prime if and only if it has no divisors $d$ that satisfy $1<d\leq \sqrt{p}$.

Exercise. Show there are infinitely many primes of the form $6k+5.$

Exercise. Show that no integer of the form $n^3+1$ is a prime, other than $2.$

Exercise. (a) Explain why $\left(a,a^2\right)=a$ where $a$ is a positive integer. (b) Explain why 201 is not a prime. (c) Explain why 11 is a prime number.

1 thought on “Prime Number Theorems (Infinitude of Primes)”

  1. My knowledge on prime numbers was limited prior to reading this article. My memory on what constituted a prime number was accurate but vague and the last time I even thought of a prime number was during my GMAT prep work. I confess that I was ignorant to Euclid’s proof that there were an infinite number of primes. I did however recall that 2 is the only even prime number. Great Article!

    Reply

Leave a Comment