Infinitely many primes
Infinitely many primes
An excerpt from Proof and the Art of Mathematics
This is a free extended excerpt from chapter 3 of my book Proof and the Art of Mathematics, an introduction to the art and craft of proof-writing, for aspiring mathematicians who want to learn how to write proofs.
Proof and the Art of Mathematics teaches the art of proof-writing in the diverse contexts of a variety of mathematical subjects, but always with mathematical theorems and statements that carry their own inherent interest and fascination—compelling mathematical results with interesting, elementary proofs.
Infinitely many primes
Let us turn now to another classical result, the fact that there are infinitely many primes. This is a classic argument, often attributed to Euclid, known for thousands of years.
Theorem. There are infinitely many prime numbers.
Proof. Suppose that you have a list of finitely many prime numbers: p1, p2, …, pn.
Let N = (p1p2 ··· pn) + 1, the result of multiplying them together and adding 1. Observe that if you should divide N by any particular prime number pi on your list, then there will be a remainder of 1. In particular, this number N is not divisible by any prime number on your list. But N is a product of primes, as every natural number is, and so there must be a prime that is not on the list. Thus, no finite list of numbers includes all the primes, and so there must be infinitely many of them. ☐
Sometimes one sees this argument given as a proof by contradiction, like this:
Proof. Assume toward contradiction that there are only finitely many primes, p1, p2, ···, pn. Multiply them all together and add one N = (p1p2 ··· pn) + 1. This new number N is not a multiple of any pi, and so its prime factorization must involve new primes, not on the list, a contradiction. ☐
Is it better to give a proof by contradiction or directly? This second proof seems perfectly fine. Euclid had not used proof by contradiction but, rather, proved that every finite list of primes can be extended. Mathematicians often prefer direct proofs over proofs by contradiction. One reason, to my way of thinking, is that direct proofs usually carry more information about the mathematical background — they paint a fuller picture of mathematical reality. When one proves an implication p ⇒ q directly, one assumes p and derives further consequences p1, p2, and so on, before ultimately concluding q. Thus, one has learned a whole context about what it is like in the p worlds. Similarly, with a proof by contraposition, one assumes the negation of the conclusion ¬q and derives consequences about what it is like in the worlds without q, before finally concluding ¬p, negating the hypothesis. But in a proof by contradiction, in contrast, one assumes something that ultimately does not hold in any world; the argument often seems to tell us little beyond the brute fact of the implication p ⇒ q itself.
Next, let us prove that although there are infinitely many prime numbers, nevertheless there are also long stretches of numbers with no prime numbers at all.
Theorem. There are arbitrarily large intervals in the positive integers containing no prime numbers.
Proof. Consider any positive integer n ≥ 2. Notice that n! + k is a multiple of k, whenever 1 ≤ k ≤ n, since in this case it is the sum of two multiples of k. By considering 2 ≤ k ≤ n, we have therefore found an interval of positive integers, from n! + 2 up to n! + n, containing no prime numbers. This interval (inclusive) has n-1 numbers in it, and so there are arbitrarily large intervals of nonprimes in the positive integers. ☐
It is natural to inquire about the density of the prime numbers. Let π(n) be the prime-counting function, the number of prime numbers p ≤ n.
The figure above illustrates the density of primes, with a narrow blue line for each prime number up to five thousand, spaced out on the number line (some selected primes are indicated in red). The pattern is irregular, with some intervals having primes clumped near each other and other intervals more sparsely populated, with perhaps a barely perceptible decay in the density as one moves to higher numbers. Since the previous theorem shows that there are large primeless intervals, we should expect to find increasing white patches, without any blue lines, if the figure were continued to larger numbers.
In contrast to the previous result, let us now provide a lower bound on the number of prime numbers. Define that a positive integer r is square-free if it is not a multiple of any square number bigger than 1; equivalently, as the reader will show in the exercises, a positive integer is square-free if all the primes in its prime factorization have exponent 1.
Theorem (Erdős). The prime-counting function π has a lower bound provided by the inequality
Proof. Every natural number can be factored as rs2, where r is square-free, as the reader will verify in the exercises. How many square-free numbers are there less than n? Well, every square-free number is a product of distinct primes, and so it is determined by the set of primes that divide it. So the number of square-free numbers up to n will be at most 2π(n), which is the number of sets of primes up to n. Second, the number of squares up to n is at most √n, since if s2 ≤ n then s ≤ √n, and s2 is determined by s. So the number of numbers up to n having the form rs2, where r is square-free, is at most 2π(n)√n. Since there are n positive integers less than or equal to n, we conclude that
Dividing both sides by √n leads to
and then taking the logarithm (base 2) enables us to conclude that
which amounts to the inequality
as desired. ☐
An arithmetic progression is a sequence of numbers of the form p, p + e, p + 2e, p + 3e, and so on. Two numbers are relatively prime if they have no nontrivial common factor.
Theorem. There are arbitrarily long arithmetic progressions consisting of relatively prime numbers.
Proof. Fix any number d, and let e = d!, the factorial of it. Let p be a prime number larger than e, and consider the numbers
in other words, the numbers of the form p + ei, where i < d. These form an arithmetic progression of length d and period e. Let me show that these numbers are all relatively prime. Suppose that q is a prime factor of two of the numbers, p + ei and p + ej, where i < j < d. It follows that q divides the difference of the two numbers, which is equal to e( j - i ). Since i and j are both less than d and e = d!, it follows that all of the prime factors of e( j - i ) are at most d, so q ≤ d. In this case, q divides e and hence ei, and since it also divides p + ei, it must be that q divides p, which is prime. So q = p, contrary to our choice of p to be larger than e. ☐
It had been a long-standing open question, since at least 1770, whether one could find arbitrarily long arithmetic progressions of prime numbers (not merely relatively prime). This much harder question was finally settled in the affirmative in a celebrated 2004 result of Ben Green and Terence Tao. The Green-Tao theorem states that for every natural number d, there is an arithmetic progression of length d consisting entirely of prime numbers.
Habits
Choose variable names well. Choose sensible variable names that help remind you of their meaning. But also try to follow established variable-naming conventions, when possible, in order to hook into your readers' expectations about what kind of quantity your variable represents. For example, many mathematicians use variables n and m to represent natural numbers or integers, while p and q are probably prime numbers, the variables x and y frequently represent real numbers, z is often a complex number, and f and g are likely functions. Conventions can vary between particular mathematical specializations.
Use technical words with accuracy and precision. Recognize that mathematical words often carry extremely precise meanings, far more explicit and detailed than the meanings conveyed in ordinary language by those words. Use technical vocabulary strictly to carry these more specific meanings.
Define your technical terms. Provide explicit formal definitions for your mathematical terms, and use the words in accordance with their definitions. Clarify undefined terms; do not allow vagueness and ambiguity to slip into your analysis simply because you have not taken the trouble to define your terms.
Try proving implications directly. When proving a statement of the form, “if p, then q,” try starting your argument by writing, “Assume p,” and then argue for q. This method is called a direct proof of the implication.
Try proving implications via the contrapositive. When proving a statement of the form “if p, then q,” consider the contrapositive, “if not q, then not p.” This is logically equivalent to the original statement and sometimes admits a smoother argument, particularly when q has a negative form, in which case “not q” becomes a positive assumption. Write, “To prove the contrapositive, assume not q.” And then argue for not p.
Exercises
Prove that a positive integer is prime if and only if it has exactly two positive integer divisors.
Show that a positive integer p > 1 is prime if and only if, whenever p divides a product ab of integers, then either p divides a or p divides b.
Prove a stronger version of Bézout's lemma, namely, that for any two integers a and b, the smallest positive number d expressible as an integer linear combination of a and b is precisely the greatest common divisor of a and b.
Read Timothy Gower's blog post, “Why isn't the fundamental theorem of arithmetic obvious?” and his follow-up post, “Proving the fundamental theorem of arithmetic.” Write a summary.
Show that if we count the number 1 as prime, then the uniqueness claim of the fundamental theorem of arithmetic would be false. (And this is one good reason not to count 1 as amongst the prime numbers.)
Prove that if one prime divides another, then they are equal. (This was used in the proof of the fundamental theorem of arithmetic.)
Mathematician Evelyn Lamb fondly notes of any large prime number presented to her that it is “one away from a multiple of 3!” And part of her point is that this is true whether you interpret the exclamation point as an exclamation or instead as a mathematical sign for the factorial. Prove that every prime larger than 3 is one away from a multiple of 3!. [Hint: Consider the remainder of the number modulo 6.]
Prove that if a, b, and c are positive integers and the product abc is a multiple of 6, then one of the numbers ab, ac, or bc is a multiple of 6.
Define that an integer is even if it is a multiple of 2; and otherwise it is odd. Show that every odd number has the form 2k + 1 for some integer k. Conclude that any two consecutive integers consist of one even number and one odd number.
Prove or refute the following: For any list of primes p1, p2, ···, pn, the number (p1p2 ··· pn) + 1 is prime.
Criticize the following “proof.” Claim. There are infinitely many primes. Proof. Consider any number n. Let n! be the factorial of n, and consider the number p = n! + 1. So p is larger than n, and it has a remainder of 1 dividing by any number up to n. So p is prime, and we have therefore found a prime number above n. So there are infinitely many prime numbers. ☐
Prove that a positive integer is square-free if and only if all of the exponents in its prime factorization are 1.
Prove that every positive integer m can be factored as m = rs2, where r is square-free. [Hint: Let r be the product of the primes having odd exponent in the prime factorization of m. Alternatively, let s be the largest number such that s2 divides m, and argue that the quotient is square-free.]
Prove or refute the following: The lower bound on π(n) provided by Erdős’s theorem is best possible, after applying the ceiling function in the integers. Make a clear theorem statement about what this means and about what exactly you are proving.
Please enjoy my musical video collaboration with Hannah Hoffman proving the infinitude of primes:
Continue reading more about this topic in my book: