Every Proof That There Are Infinitely Many Primes Explained

What Is a Prime Number?

Think of a natural number. That is, a number used for counting, like six. Next, think of another natural number, like two. If we calculate 6 / 2, the result is 3. Since 3 is also a natural number, we say that 2 divides 6, that 6 is divisible by 2, or that 2 is a divisor of 6. Put another way, 2 × 3 = 6. When you multiply numbers together, those numbers are called factors. So two can also be called a factor of six.

A prime number is a natural number that has exactly two factors. Those factors are always the number one and the prime number itself. An example of a prime number is seven, whose only factors are 1 and 7. Note that the number one is not a prime number. Its only factor is one itself, so it does not have two factors.

In contrast to prime numbers, a composite number is a natural number that you can get by multiplying two smaller natural numbers. Since those natural numbers are factors of the composite number, a composite number always has factors other than one and itself. Every natural number greater than one is either prime or composite, and a composite number can always be expressed as a product of prime numbers.

Now here is a question. How many prime numbers are there? This was something the ancient Greek mathematician Euclid wanted to know. And eventually he found the answer. There are infinitely many prime numbers. This is a theorem, a mathematical statement that can be proven to be true. In honor of the person who proved it, this theorem is called Euclid’s theorem.

Euclid’s Proof

Let’s look at a condensed version of Euclid’s proof, taken from the Elements, a mathematical work written by Euclid.

To start, take some finite set of prime numbers. An example would be the set {2, 3, 7}. Note that we do not need to include all of the prime numbers in a given interval. Our goal is to prove that there is some prime number that we have not included.

To do that, multiply all of the prime numbers in this set together. That is, take their product. After you do that, add one to the result. Here, that gives us 2 × 3 × 7 + 1 = 42 + 1 = 43.

Is this number prime? In this case, 43 does happen to be a prime number. So we found a prime number that is not in our set, and we are done.

However, what if this is not the case? For example, imagine starting with the numbers 3, 5, and 7 instead. The product of these numbers is 105. If we add 1, we get 106. This number is composite, not prime. However, notice that 106 has prime factors, those being 2 and 53, that are not any of the prime numbers in our starting set.

To see why, remember that we calculated 3 × 5 × 7 to get 105. By definition, 3, 5, and 7 are factors of 105. If one of those were also a factor of 106, then it would have to be a factor of 106 − 105 as well. But 106 − 105 = 1. And the number one has no factors other than itself. So this is not possible.

Generally, if you have a finite set of prime numbers, then taking their product and adding one will give you a number that has prime factors entirely different from the prime numbers in the original set. For each finite set of prime numbers, we will always be able to find another prime number which is not in that set. Since no finite set can contain every prime number, the set of prime numbers must be infinite.

Factorial Proof

In the natural numbers, there is a function called the factorial, written with an exclamation mark. To demonstrate, let’s calculate 4!. We simply multiply together every positive natural number which is less than or equal to 4, giving a result of 24.

Now think about calculating 4! + 1. Notice that 25 is not divisible by any natural number from 2 to 4. We got 24 by multiplying every natural number from 1 to 4, so each of those numbers must be a factor of 24. In order for one of those numbers to be a factor of 25 as well, it would also have to be a factor of 25 − 24. That is equal to 1. And the only factor of the number 1 is itself.

We do know that 1 is a factor of 25, since 1 is a factor of every natural number. But 2, 3, and 4 cannot be factors of 25. So 25 must have a prime factor greater than four. Indeed, we can calculate that 25 has the prime factor 5, which is greater than 4.

Instead of four, we can use any positive natural number we want and the same logic will still apply. When we take the factorial of that number and then add one, we will always get a number whose prime factors are greater than the number we started with. There is no bound on how large a positive natural number can be, so there must also be no bound on how large a prime number can be. Once again, we conclude that there must be infinitely many prime numbers.

Erdős’s Proof

This final proof is taken from Hungarian mathematician Paul Erdős. He is rather famous in the world of math. He collaborated on so many research papers that the concept of an Erdős number was invented, categorizing how closely linked a given person is to Erdős by paper collaborations.

Let’s start by defining a few terms. Pick a whole number and multiply it by itself. The result is called a square number. For example, 6 × 6 = 36, so 36 is a square number. This can also be expressed using exponentiation, which is repeated multiplication. 6² (also pronounced “6 squared”) is equal to 6 × 6 = 36. Geometrically, a square whose side length is 6 units has an area of 36 square units, which is why we use the word “square.”

The number one is a square number because 1² = 1. Also, the number one is a factor of every whole number. Sometimes a whole number has no square number factors except the number one. This is called a square-free number.

For example, consider the number 30. We can quickly figure out whether this number is square-free by writing its prime factorization: 2 × 3 × 5. No prime factor appears more than once, so we cannot form a square number with them. So 30 is square-free.

As another example, take 24, which equals 2 × 2 × 2 × 3. We can rewrite this as 2 × 3 × 2 × 2. Now 2 × 2 = 4 is a square number that is a factor of 24. So 24 is not square-free.

Every positive whole number can be expressed as a product of a square number and a square-free number. Using our example of 24, we can divide it by its largest square number factor, which is 4. That gives us 24 / 4 = 6. Now we can reverse this statement: 6 × 4 = 24. As you can see, 6 is a square-free number, 4 is a square number, and we have successfully written 24 as the product of these numbers.

Even a square-free number can be expressed as itself × 1. For example, 30 × 1 = 30. Also, a square number can be expressed as 1 × itself. For example, 1 × 9 = 9. In both cases, this is still a square-free number times a square number.

Let’s call the square-free factor r and the square factor s². Now that we have the pieces in place, it is time to pick a positive whole number, which will be called n. Let’s choose n = 16. How many prime numbers are less than or equal to 16? The answer is 6, and we will call that number k. Specifically, the prime numbers are 2, 3, 5, 7, 11, and 13.

Next, consider a whole number called a which is less than or equal to our chosen number n. For example, a = 14. This number can be expressed in the form r × s². That is, a square-free number times a square number. In this case, that is 14 × 1². So r = 14 and s = 1.

Notice a special property of the number r. Whatever value of a we choose, r will always be a product of prime numbers which are less than or equal to n, and each prime number will appear at most once. In this case, the prime numbers are 2 and 7, and each of them is less than or equal to 16.

In some cases, the square-free factor r will actually be equal to 1. For example, when a = 9, we express 9 as 1 × 3². So r = 1 and s = 3. In this case, it is obtained by multiplying no prime numbers together. The result of multiplying no numbers is called the empty product, and it is equal to one.

Because the number r has this property, it is always given by a certain subset of the set of prime numbers which are less than or equal to n. Our n = 16 example has six prime numbers less than or equal to n. In other words, these six prime numbers are the six elements of our set.

Here we can use a rule for sets. If you have a set, then the number of subsets equals 2 to the power of the number of elements in the set. This is because when you create a subset, you have to choose whether or not to include each element of the original set, and each choice multiplies the number of possibilities by two. In our example, we have a set with six elements, so the number of possible subsets is 2⁶ = 64. Generally, if there are k prime numbers less than or equal to n, then the number of possible subsets is equal to 2ᵏ. The number of possible values of r must be less than or equal to 2ᵏ.

Next, we focus on the s² part. Remember that r × s² has to be less than or equal to n. So s² also has to be less than or equal to n. Because of this, s has to be less than or equal to √n. That is, the non-negative number that when squared gives you n.

Using an earlier example, we had that 1 × 3² is less than or equal to 16. So 3² by itself is less than or equal to 16. The square root of 16 is equal to 4 because 4² = 16. Plugging the numbers into the inequality s ≤ √n, we get 3 ≤ 4, which is true. That is just one example, but the inequality will always be true no matter what numbers you plug in for s and n. In fact, you can choose a value of n that is not a square number, even though that means √n will not be a whole number.

To recap, we now know that the number of possible ways to choose the value of r must be less than or equal to 2ᵏ. And the number of possible ways to choose the value of s must be less than or equal to √n. So what do we know about the number of possible ways to choose both r and s? First, it must be less than or equal to 2ᵏ × √n. Secondly, each way corresponds to exactly one positive whole number which is less than or equal to n. So the total number of possible ways must be exactly equal to n.

So n ≤ 2ᵏ × √n. We can divide both sides of this inequality by √n, and we get √n ≤ 2ᵏ.

To finish the proof, we need one final observation. We can make √n as big as we want. If we choose n = 1,000,000, then √n = 1,000. If we choose n = 1,000,000,000,000, then √n = 1,000,000. As n gets larger and larger, we also need k to get larger and larger so that the statement √n ≤ 2ᵏ stays true. Because of this, there is no upper bound to how large k can get. In other words, since we defined k as being equal to the number of primes that are less than or equal to n, there is no upper bound on how many prime numbers you can have in a set. So there are infinitely many prime numbers.

---

This article was generated from the video transcript of “Every Proof That There Are Infinitely Many Primes Explained”.
Watch the full video above for visual explanations and diagrams.