Prove: There are infinitely many prime numbers.

How do we even start proving that something is infinite? For instance, how do we show that there are infinitely many prime numbers?

The premise in itself is so mind-boggling because the concept of infinity is vast and at its very core, very daunting to comprehend. However, we have an intuition that the sequence of prime numbers which starts at [latex]2[/latex] goes on forever without bounds.

Having an intuition that there are infinite primes is one thing, but proving it that it’s indeed true is another.


BRAINSTORM BEFORE WRITING THE PROOF

brainstorm before writing the proof

Note: The purpose of brainstorming in writing proof is for us to understand what the theorem is trying to convey; and gather enough information to connect the dots, which will be used to bridge the hypothesis and the conclusion.

Since the focus of the proof in this lesson is about primes, it is important that we first define what a prime number is.

DEFINITION: A prime number is a positive integer that is greater than [latex]1[/latex], and it has exactly two factors which are [latex]1[/latex] and itself.

Below is another definition of a prime number, [latex]\color{red}p[/latex].

a prime number p belongs to the set of positive integers where p>1 and whose only two factors are 1 and p

So the positive integer [latex]\large1[/latex] is not a prime number because a prime number by definition is a positive integer that is greater than [latex]1[/latex].

In addition, [latex]1[/latex] is not a composite number either because a composite number is also a positive integer that has at least one divisor other [latex]1[/latex] and itself. In fact, the number [latex]1[/latex] is neither prime nor composite.


It’s a good practice for us to gain a basic understanding on how to manually identify a prime number.

number 7

Our goal is to list the first seven prime numbers. Let’s do that by counting up starting from the number [latex]2[/latex] then test each number for its primality.

The first seven prime numbers

  • [latex]\large\red2[/latex] is a prime number since it has exactly two divisors, namely [latex]1[/latex] and itself, [latex]2[/latex]. In fact, it is the smallest prime number, and also the only even number that is prime.
  • [latex]\large\red3[/latex] is a prime number because its only factors are [latex]1[/latex] and [latex]3[/latex].
  • [latex]\large4[/latex] is NOT prime because it has another factor other than [latex]1[/latex] and itself. The other factor is [latex]2[/latex]. We say that it is a composite number.
  • [latex]\large\red5[/latex] is prime for the obvious reason that its only factors are [latex]1[/latex] and itself.
  • [latex]\large6[/latex] is NOT prime because its two factors other than [latex]1[/latex] and itself are the prime numbers [latex]2[/latex] and [latex]3[/latex].
  • [latex]\large\red7[/latex] is a prime number because the only two divisors are [latex]1[/latex] and [latex]7[/latex].
  • [latex]\large8[/latex] is NOT a prime number for the same reason that it has more than two factors.
  • [latex]\large9[/latex] is NOT a prime number because perfect squares are not primes. Notice that [latex]9 = 3 \times 3 = {3^2}[/latex]. It clearly has a factor other than [latex]1[/latex] and [latex]9[/latex].
  • [latex]\large10[/latex] is NOT prime because it is a product of two other prime numbers, [latex]2 \times 5 = 10[/latex]. That means [latex]10[/latex] has more than two factors which are [latex]1[/latex], [latex]2[/latex], [latex]5[/latex], and [latex]10[/latex].
  • [latex]\large\red{11}[/latex] is a prime number since its only factor pair includes [latex]1[/latex] and [latex]11[/latex]; thus, [latex]1[/latex] & [latex]11[/latex].
  • [latex]\large12[/latex] is NOT a prime number because it is an even number larger than [latex]{2}[/latex].
  • [latex]\large\red{13}[/latex] is definitely prime since its only factors are [latex]1[/latex] and itself.
  • [latex]\large14[/latex], [latex]\large15[/latex] and [latex]\large16[/latex] are composite numbers therefore they are not primes. I will leave it to you to verify.
  • [latex]\large\red{17}[/latex] is a prime number since it can only be divided by [latex]1[/latex] and [latex]17[/latex].

the first seven prime numbers are 2, 3, 5, 7, 11, 13 and 17

I just hope that this little exercise of finding the first seven prime numbers by hand gives us an appreciation that finding prime numbers can be tedious. In fact, it’s extremely tedious because as prime numbers become infinitely large, their gaps also become infinitely humungous.

Suppose that we continue the process of manually finding prime numbers using the list method above.

Assume that we stumble upon the prime number [latex]\large\red{{p_n}}[/latex]. We try our best to find the next prime number after [latex]\large{{p_n}}[/latex] but we fail every time. Thus, we categorically declare that there’s no more prime number after that. The end!

How can we be so sure that [latex]\large\red{{p_n}}[/latex] is indeed the largest prime?

Now, we are getting into the strategy of proving that there is an infinite number of prime numbers.

Firstly, trust me that there’s no way to prove it using direct proof since it is impossible to come up with a sensible hypothesis to start with, and use it as a basis to arrive at the conclusion. Hence, we are going to prove it is using the proof by contradiction.


  • The original statement that we want to prove:

There are infinitely many prime numbers.

  • Claim that the original statement is FALSE then assume that the opposite is TRUE. The opposite of the original statement can be written as:

There is a finite number of primes.

  • Let’s see if this makes sense. Assume that there is a finite amount of prime numbers, and the only prime numbers in existence are listed below. Keep in mind that the largest prime number is [latex]17[/latex].

[latex]\large{2,\,\,3,\,\,5,\,\,7,\,\,11,\,\,13,\,\,17}[/latex]

  • Construct the new number [latex]\Large{x}[/latex] by multiplying all the prime numbers then add [latex]\large{\red{1}}[/latex] to the product.
x=2*3*5*7*11*13*17+1=510,511
  • Now, what can we say about the number [latex]{x}[/latex] ? We know that it does not equal [latex]1[/latex] since [latex]x>1[/latex]. Can [latex]{x}[/latex] be a prime number? The answer is a big no because we assume already that we have all the prime numbers or the most complete list of all primes namely, [latex]\large{2,\,\,3,\,\,5,\,\,7,\,\,11,\,\,13,\,\,17}[/latex]. By elimination, it is safe to say that [latex]{x}[/latex] must be a composite number.
  • Since the number [latex]\Large{x}[/latex] is a composite number (a positive integer having at least one factor other than [latex]1[/latex] and itself), it must be divisible by at least one of our prime numbers on the list.
  • Now it’s time to check the divisibility of each prime number in our list with the value of [latex]\large{x}[/latex] which is [latex]510,511[/latex] as calculated above.

The symbol [latex]\large\nmid[/latex] is read as “does not divide”.

[latex]2\,\nmid \, 510,511[/latex] [latex]\rightarrow[/latex][latex]\,2[/latex] does not divide [latex]510,511[/latex]

[latex]3\,\nmid \, 510,511[/latex] [latex]\rightarrow[/latex][latex]\,3[/latex] does not divide [latex]510,511[/latex]

[latex]5\,\nmid \, 510,511[/latex] [latex]\rightarrow[/latex][latex]\,5[/latex] does not divide [latex]510,511[/latex]

[latex]7\,\nmid \, 510,511[/latex] [latex]\rightarrow[/latex][latex]\,7[/latex] does not divide [latex]510,511[/latex]

[latex]11\,\nmid \, 510,511[/latex] [latex]\rightarrow[/latex][latex]\,11[/latex] does not divide [latex]510,511[/latex]

[latex]13\,\nmid \, 510,511[/latex] [latex]\rightarrow[/latex][latex]\,13[/latex] does not divide [latex]510,511[/latex]

[latex]17\,\nmid \, 510,511[/latex] [latex]\rightarrow[/latex][latex]\,17[/latex] does not divide [latex]510,511[/latex]

  • In summary, there exists no prime number in our finite list of primes that can evenly divide the constructed number [latex]\Large{x}[/latex] with a value of [latex]510,511[/latex]. Notice that there is always a remainder of [latex]\color{red}1[/latex].
  • We have reached a contradiction because it implies that we don’t have a complete list of all the prime numbers. In addition, since [latex]\Large{x}[/latex] is a composite number, there exists a prime number greater than [latex]17[/latex], the largest prime number in the list, that can divide it evenly.
  • Therefore, we say that our assumption that there is a finite number of prime numbers is false. This leads us to conclude that the original statement must be true which states that there are infinitely many prime numbers.

WRITE THE PROOF

THEOREM: There are infinitely many prime numbers.

PROOF: Firstly, we claim that the original statement is false. Secondly, we are going to assume that the opposite is true. That is, we assume that there is a finite number of prime numbers. We say there are only [latex]\large{n}[/latex] prime numbers. Let’s designate them with the variable [latex]\large{p}[/latex] with subscripts [latex]1[/latex], [latex]2[/latex], [latex]3[/latex], [latex]4[/latex], and so on. Since the set of prime numbers is assumed to be finite, the largest prime will take the subscript of [latex]n[/latex]. Listing them, we have [latex]{p_1},\,\,{p_2},\,\,{p_3},\,\,{p_4},\,\, \cdot  \cdot  \cdot \,\,,\,\,{p_{n – 1}},\,\,{p_n}[/latex]. Now, we construct a new number [latex]\large{x}[/latex] by multiplying all the prime numbers then adding [latex]\red{+1}[/latex] to the product.

[latex]\large{x} = {p_1} \times {p_2} \times {p_3} \times {p_3} \times \,\, \cdot  \cdot  \cdot \,\, \times \,\, {p_{n – 1}} \times {p_n}\color{red} + 1[/latex]

There are two possibilities of the value of [latex]\large{x}[/latex]. It can either be a prime number or a composite number. Clearly, [latex]x[/latex] cannot be prime since we already assume that we have all the primes which can be written as [latex]{p_1},\,\,{p_2},\,\,{p_3},\,\,{p_4},\,\, \cdot  \cdot  \cdot \,\,,\,\,{p_{n – 1}},\,\,{p_n}[/latex]. This means [latex]x[/latex] must be a composite number, thus at least one of the prime numbers can evenly divide it. Let’s represent all primes in the list as [latex]{p_k}[/latex] where [latex]{1 \le k \le n}[/latex]. However, [latex]{p_k}[/latex] does not divide [latex]{x}[/latex] since we always get a remainder of [latex]{1}[/latex] when we divide [latex]{x}[/latex] by [latex]{p_k}[/latex]. This is a contradiction to the assumption that we have all the prime numbers in the list which implies our list of prime numbers is incomplete. Therefore, we reject the assumption that there are finitely many prime numbers, and thus conclude the original statement must be true. We have just proved there are infinitely many prime numbers. ◾️