The infinitude of prime numbers

As a Mathematics graduate student, I am continuously exposed to the most profound mathematical thoughts. I have never ceased to be amazed by the beauty of the arguments constructed for proving the lemmas and the theorems. One thing, I keep noticing, as I advance through the program; once you peel off the layers, the actual ideas that are employed do not change a lot regardless of how advanced the mathematics. I am not implying here that you don’t learn new ideas - that certainly becomes a part of the toolkit you carry, but there is a “reasonably” small (ill-defined) set of ideas which keep recurring. (This is a reason why I think Professors are able to set examination or homework questions, since its often easy to “predict” knowing the mathematical maturity of a student, how much time the said student would need to solve a relatively standard problem. Though I don’t think this is always as straightforward in abstract Mathematics as with, for instance, Calculus problems wherein you have a finite set of algorithms in your repertoire to tackle all the problems. Given the increasingly interdisciplinary nature of abstract mathematics, a problem solver has a much bigger pool of ideas to choose from and trial and error is no longer a viable option). The larger change you see is in terms of breadth and depth of information that you are supposed to know. The complexity of the structures to be analyzed keeps increasing as well. Several smaller ideas get combined into one. Ultimately though, when you sit down to solve a problem, you break it down into mini-problems and then each mini problem is usually tackled using methods you have known for some time. The open endedness of Mathematics usually comes from how well this splitting is done.

My hope is to create a series of articles in which I present proofs of some propositions/theorems that have fascinated me over and over again. The striking features in these are the simplicity, beauty and ubiquity of ideas involved. I am also trying to make these articles accessible to a general audience so there are only bare minimum assumptions on the reader’s background. That being said, some of my “definitions” might not appeal to the mathematical purists, but that is a risk I am willing to take. Another (selfish) reason to write these proofs is to see exactly which ideas seem obvious to a general reader. I have frequently struggled to understand mathematical arguments which the presenter has deemed to be trivial.

The first area of mathematics that truly attracted me was number theory. It is perhaps best to start with probably one of the most elegant arguments in number theory and perhaps also in all of mathematics.

Euclid’s theorem: There are infinitely many primes.

I would like to elaborate on the two key mathematical words here. A prime number p is a positive integer (integer is the set of numbers 1, 2, 3 and so on, along with their negative counterparts -1, -2, -3, … and finally 0) such that the only way to express it as a product (the product of two numbers is the operation of multiplying those numbers) of two numbers pX1 (I shall use capital X for multiplication. Technically, there is one more way of expressing the prime as a product of two numbers, viz. 1Xp, but we shall ignore the ordering of the numbers in the product and only consider the actual numbers involved). For example, 2, 3, 5 are the first three primes. They cannot be written as a product of two numbers unless one of them is the number itself (and the other being 1). On the other hand, 4, 6, 8, 9, 10 are the first five non-prime numbers (called composite numbers. We have 4=2X2, 6=2X3, 8=2X4, 9=3X3. The number 1 is not classified as a prime or a composite number. The fundamental theorem of arithmetic states that every number can be written as product of prime numbers in exactly one way (ignoring the ordering in the product).

The other concept in the theorem is that of infinity. In this context, it simply means that we can find more prime numbers than any specified number. For instance, if a random person on the street, approaches you and claims there are only 23438430 primes, then you can (after understanding the following proof), respond by saying you can easily produce more primes than that.

The argument of the proof is by Euclid (hence the name of the theorem, though the credit system in mathematics does not always work this way). The technique is called proof by contradiction (reduction ad absurdum). The idea is the following:

1. Assume the statement to be proved is false.

2. Make logical implications from the assumed statement (the negation of the original statement) using any other known facts that do not involve the statement to be proven explicitly or implicitly.

3. Arrive at a contradiction i.e. at a statement or statements known to be false.

Finally, I present (possibly slightly modified) Euclid’s argument for the proof:

1. Assume there are only finitely many primes. Let us call this number N. Now suppose these prime numbers are p­₁, p₂, …,p_N.

2. Consider the number p= p­₁Xp₂X …,Xp_N+1 i.e. p is the product of the first n primes added to one. Now there are two possibilities. Either p is itself a prime, in which case, we have found a prime greater than p_N, since we have multiplied positive numbers and added one. Else p is not prime and hence we can write it as a product of prime numbers by the fundamental theorem of arithmetic stated above. Then any prime number that appears in this product (and hence divides p), cannot be one of the list p­₁, p₂, …,p_N. If this were the case and suppose if p_r, a prime in the list divides p, then p_r must also divide p- p­₁Xp₂X …,Xp_N=1. But since every prime is greater than 1, it cannot divide 1. So in either case we have a contradiction.[End of Proof]

This concludes my discussion on one of the first ideas that exposed me to abstract mathematics and began my journey into this beautiful subject. I hope the discussion is self-contained.