The Infinity of Primes

Last week, I was teaching my class about the prime numbers – the positive integers greater than $1$ that are divisible only by $1$ and themselves. For example, $3$ is prime because it has no whole number factors other than $1$ and $3$. The whole number $6$, however, is composite – not prime. Why is $6$ not prime? Because $6$ is divisible by both $2$ and $3$, neither of which is $1$ or $6$.

It can be shown that $3$ has no whole number factors other than $1$ and $3$ by dividing it by every whole number less than $3$, except $1$. We do not need to check that $3$ is divisible by itself or $1$ because every whole number is divisible by itself and $1$.

The only number less than $3$ that is not $1$ is $2$. So, let me divide $3$ by $2$. Well, $\frac{3}{2} = 1 r 1$, where $r 1$ denotes a remainder of $1$. If a quotient has a remainder other than $0$, or some other factor of the dividend then the divisor does not divide the dividend. Thus, $2$ does not divide $3$ and is not a factor of $3$. Then, because any factor of $3$ must be less than $3$, and no number less than $3$ is a factor of $3$, $3$ is prime.

I choose to write quotients, such as $\frac{m}{n}$, in which $n$ does not divide $m$, as a result with remainder because that is how divisibility is defined.

An Important Note

We define $1$ to be neither prime nor composite (if a number other than $1$ isn’t prime, it’s composite) even though it has only $1$ and itself  as factors. We do so because we need $1$ to be non-prime. Were $1$ prime, the absolutely vital Uniqueness of Prime Factors Theorem which states that every positive integer greater than $1$ can be written as the product of a unique set of prime numbers would fail. Why? Consider the prime factorization of $8$. $8 = 2 \times 2 \times 2$. However, suppose we allow $1$ to be defined as prime. Then

$$8 = 2 \times 2 \times 2 \times 1$$

and,

$$8 = 2 \times 2 \times 2 \times 1 \times 1$$

and,

$$8 = 2 \times 2 \times 2 \times 1 \times 1 \times 1$$

And so on, ad infinitum. This would contradict the Uniqueness of Prime Factors Theorem. We solve this conundrum by simply defining $1$ to be neither prime nor composite. (We designate $1$ a unit of the whole numbers.)

Many, if not most, people not formally trained in mathematics believe that mathematics is cut-and-dried – there is one, and only one, way to work a math problem; one, and only one, set of mathematical facts – and they are fixed, and that every civilization anywhere in the universe that creates mathematics must ultimately create the exact same mathematics. Nothing could be farther from the truth. It is not at all unusual for the community of mathematicians to simply redefine some mathematical concept in order to force some theoretical outcome. The redefinition of $1$ as a unit rather than a prime is but one such example.

As the lesson hook in my lesson on prime numbers,  I asked the class whether there is a finite number of prime numbers, an infinite number of prime numbers, or if it were impossible to determine whether there are finite or an infinite number of primes.

As I have come to expect, my class eventually agreed that it is impossible to know whether there are a finite or an infinite number of primes. Their reasoning was along the lines of, “since there is an infinite number of whole numbers, we can never check them all to see how many are prime.” This is actually, for students the ages of mine, not a bad guess. It is not, however, a solution arrived at by any deductive logical argument, which is what we want students to use to come to a valid conclusion. It also has the disadvantage of being false.

There are an infinite number of primes, and it can be proven that there are. One of the proofs, a classic, is detailed below.

The Infinity of the Primes Theorem and a Proof

Claim:

The set of primes is infinite.

Explanation of the method of proof:

Let’s consider some set of successive prime numbers, beginning with the number $2$. Their product plus $1$ is necessarily prime. Why? An explanation follows.

This shall be a proof by contradiction. Some statement is assumed to be true, and via a series of logical statements, the assumption is contradicted (contra – against, diction – to speak.) Thus, the original assumption is false and its negation is true.

Suppose $2$ is the only prime number. This would imply that every successive number is a multiple of $2$. However, $2 + 1$ cannot be a multiple of $2$ because $\frac{2 + 1}{2} = 1 r 1$. That is, $(2 + 1)$, when divided by $2$ does not have a remainder of $0$, it has a remainder of $1$. (This is the definition of even and odd numbers, by the way.)

Perhaps $2 + 1$ is a multiple of some other prime number. What could that number possibly be? First, we have claimed that $2$ is the only prime number. Second, any prime number other than $2$ that divided $2 + 1$ would necessarily be less than $3 = 2 + 1$. But, $3$ is the next whole number after $2$. There is, then no number other than $2$ that is also less than $3$ and a factor of $3$. Hence, $3$ must be prime. I understand perfectly that the argument in this paragraph is difficult for some readers to follow. It is important that it is understood. The remainder of the argument follows the same logic. Take the time to re-read it until you understand the argument.

Here it is in simplified form. We claim $2$ is prime and that it is the only number that is. (In fact, since it is the least number that could possibly be prime, it must be prime.) Then, we examine the next number, $2 + 1$. This is the number $3$. Because it differs from $2$ by $1$ rather than some multiple of $2$, it cannot be a multiple of $2$. There is, in fact, no number between $2$ and $3$ that could divide $3$. Hence, $3$ has no divisors other than $1$ and itself. It is, therefore prime.

So, maybe $2$ and $3$ are the only primes. Consider $(2 \times 3) + 1$. Were $(2 \times 3) + 1$ not prime, it would necessarily be divisible by some prime number other than $1$ and itself, i.e., $2$ or $3$ or both. But, if we divide $(2 \times 3) + 1$ by either $2$ or $3$, we have a remainder of $1$.

$$\frac{(2 \times 3) + 1}{2} = 3 r 1$$

and

$$\frac{(2 \times 3) + 1}{3} = 2 r 1$$.

Thus, since $(2 \times 3) + 1 = 7$ Could it be that $7$ is prime?

Why? None of the other (supposedly) exhaustive set of prime numbers (here $2$ and $3$) could possibly divide $7$. In both cases, there is a remainder of $1$.

This does not imply that $7$ is the next prime number (after $3$.) We must check the numbers between $3$ and $7$ for primness. Dividing each of these numbers by $2$ and $3$, we find that $5$ is the only one not divisible by either. Thus, $5$ is prime.

Thus, we know that $2, 3, 5$, and $7$ are successive primes. Let us assume they are the only primes. If we examine the number $(2 \times 3 \times 5 \times 7) + 1$, we see that dividing this number by any of $2, 3, 5$, or $7$ – presumably the only primes – yields in each case a remainder of $1$. That is, $(2 \times 3 \times 5 \times 7) + 1$ is not a multiple of any prime. Thus, it is prime.

This scheme can be abstracted in the following way; suppose the following $n$ numbers

$$p(1), p(2), p(3), …, p(n)$$

are $n$ successive prime numbers, and that they are all of the prime numbers, i.e., there are no other prime numbers. (If this is the case, then there is a finite number of primes. If we can show that this assumption leads to a contradiction because $n$ can be any whole number I chose, there is not a finite number of primes – the set of primes is infinite.)

Assumption:

The set of primes is finite, and consists only of the prime numbers

$$p(1), p(2), p(3), \ldots p(n)$$

where n is any whole number greater than $1$.

Proof of the Theorem:

Consider the value of

$$[p(1) \times p(2) \times p(3) \times \ldots \times p(n)] + 1$$

Dividing this value by any of the n numbers we have assumed to be the complete set of primes, we get a remainder of $1$. In other words, the value

$$[p(1) \times p(2) \times p(3) \times \ldots \times p(n)] + 1$$

is not divisible by any of the numbers $p(1), p(2), p(3), \ldots p(n)$ we have presumed to be all of the primes. Thus,

$$[p(1) \times p(2) \times p(3) \times \ldots \times p(n)] + 1$$

is also prime.

This shows that the statement the primes are finite is false. Hence, the negation of the statement is true – the primes are infinite is true.

q.e.d. <– This is what Mathematicians write to say, “I’m done, now.” It comes from Latin and means:

 Quod Erat Demonstrandum,

or, the thing is shown (demonstrated).

Euro (nee Mark)