# Part 3ii: Introduction to Prime Numbers

### Further Reading:

## Goldbach’s Conjecture:

If you would like to extend your discussion of primes with an activity that can both enhance your students’ understanding of prime numbers and expose them to the larger mathematical world, consider Goldbach’s conjecture. Before we give the statement, we start with a bit of background. As we have stated several times in the clips, a statement is considered ‘true’ in mathematics if a proof of its validity can be provided. Mathematical statements for which a proof can be provided are called theorems (for example, the Pythagorean Theorem is a statement about right triangles that has a proof). Other words that describe statements that have proofs are proposition, lemma, corollary, etc.

A statement which is thought to be true, but for which no proof has been provided, is called a conjecture. The statement we will consider that is attributed to the 18^{th} century German mathematician Christian Goldbach is such a statement; even though the statement was first posed in 1742, no proof has yet been demonstrated, making it one of the oldest unsolved problems in all of mathematics. The beauty of the statement is that it is understandable to any elementary student who knows the definition of a prime number; thus making such a discussion grade appropriate. Without further ado…

**Goldbach’s conjecture: Every even number greater than 2 can be expressed as the sum of two prime numbers.**

**This is easy to verify for small numbers: **

**And it isn’t too difficult for somewhat larger numbers:**

But simply verifying that this can be done for specific even numbers greater than 2 cannot serve as a proof, as there are infinitely many even numbers to check. (Note: At present the conjecture has been verified by computer for all even numbers up to roughly 1,609,000,000,000,000,000. This still doesn’t count as a proof!)

A nice elementary school exercise could be to do what we did above; give your students a handful of (relatively small) even numbers, and have them express their numbers as a sum of two primes. This is a nice way to get students thinking about which numbers are prime and which aren’t, and it also allows you an opportunity to talk about the notion of mathematical proof, as well as a very famous historical problem!

**Infinitude of Primes**

One of the first activities students typically see after being introduced to prime numbers is to simply determine which numbers are prime and which are not. This is often done with a ‘prime number sieve’, which is how the definition of prime number was motivated in the preceding clip. This type of exercise inevitably leads to larger questions about primes, chief among them being, ‘How many prime numbers are there?’ Specifically, are there finitely many or infinitely many prime numbers? (Admittedly the concept of ‘infinitely many’ is hard enough for adults to wrap their heads around. However an analogy involving whole numbers can be made, as there are infinitely many whole numbers.) An equivalent question that might be easier to grasp could be ‘Is there a largest prime number?’ If the answer to this question is yes, then there would be finitely many prime numbers, and if the answer to this question is no that would imply that there are infinitely many primes.

Without thinking about the matter too deeply, it seems that reasonable arguments could be made to support either conclusion. On the one hand, there is no largest whole number, so maybe there is no largest prime number. On the other hand, all it takes for a number to be composite (not prime) is for it to have one measly factor other than itself and 1. So it seems like it would be really hard for a very large number to be prime, as there are so many numbers (2 through ) that could be divisors, and if just one of them is a divisor then would not be prime. Also, in the next clip we will show that there exist sequences of any length imaginable containing consecutive composite numbers, which implies that far more numbers are composite than prime. So, which answer is correct, and more importantly, why?

Euclid published the correct result, that there are infinitely many primes, in his famous text Elements. There are many known proofs of the result, and the one I give below is perhaps the most ‘user-friendly’. It is based on the proof technique called ‘proof by contradiction’, which essentially says that if an assumption leads to a contradiction (false statement) the assumption must be false, which implies that its negation (opposite) is thus correct.

As a very simple example of a proof by contradiction, suppose we wanted to prove that for all real numbers . Now this result is obviously true, but how could we prove it? One way would be to use contradiction. Let’s start by assuming the result is false, i.e. that for some real number . But if we now subtract from both sides of this inequality, we reach the absurd statement . Since our assumption that led to the contradiction , we must conclude that is false, and therefore its negation, must be true. Of course this seems like a ridiculously involved way to prove such an obvious result, but hopefully it illustrates the logic behind the technique of contradiction.

So to prove that there are infinitely many prime numbers, we are going to begin by assuming the opposite, i.e. that there are finitely many prime numbers. As mentioned earlier this is equivalent to assuming there is a largest prime number. Under this assumption, we may list all of the primes in increasing order; let’s call them , with being the smallest prime (i.e., 2) and being the largest prime, which exists under our assumption. (Note: All we are assuming is that there are finitely many primes; since we don’t know exactly how many there are, we just assume that there are of them.)

As we saw with our earlier example, we need this faulty assumption to lead us to a contradiction. To obtain our contradiction, consider the following number: the product of all of the primes in our list, plus 1: . Now this equation is certainly equivalent to . Now must be divisible by some prime (the Fundamental Theorem of Arithmetic states that every whole number greater than 1 can be expressed as a product of primes, and as a result is divisible by a prime), but since we assumed that the only primes are , must be divisible by one of these numbers. But this is impossible, because if were divisible by some prime in that list, the entire right hand side of the equation would be divisible by that prime (since by its very construction is divisible by **all** primes), and as a result would be divisible by that prime. But the only divisors of are and , neither of which are prime.

So our assumption that there are finitely many primes leads us to a contradiction, and therefore we must conclude that that assumption is flawed. As a result, the negation of that assumption must be correct; therefore there must be infinitely many primes!