Thursday 27 October class

Topics:
• Outlining the proof that there is no largest prime number

For this purpose the best source to use is Delphi For Fun on Proof by Contradiction, which explains a bit of the logic behind proofs by contradiction. You may then also want to look at these sources:

Why are there infinitely many prime numbers? (from Peter Alfeld, University of Utah)

Euclid's proof that there are an infinite number of primes (from Susan Stepney, University of York, UK) - this one, beware: the part below the line, where it says "for example", is not part of the proof!

And also the sources linked below...

• How Euclid (and those of his time and place) conceived of the proof and their concept of "number":
See Cut-The-Knot, which gives alternate versions of the proof as well,but is rather technical: and also the proof as described in the Prime Number Pages, which describes how Euclid would have thought of numbers.

Here is the outline of the proof we developed in class. I've put an asterisk * next to parts that need proving but are not proved in any of the sources linked above, for some reason. We did the proofs of those parts in previous classes.

To prove: there is no largest prime number

Proving by contradiction (reductio ad absurdum): we will assume the opposite, and show that assumption leads to a contradiction.

Outline of Proof: 
• Assume that there is a largest prime number. Call it p.
   [Note: either there is a largest prime number, or there is not a largest prime number. There is no other possibility. This is important for the logic of the proof.]
Commentary: This assumption puts us into an alternate universe, not the one we actually live in. The rest of this proof will be showing that that alternate universe cannot exist. In that alternate universe, we know everything else we know about prime numbers from our universe, including the Fundamental Theorem of Arithmetic (Unique Prime Factorization), but we are assuming that in that universe there is a largest prime number.

OK, now in the alternate universe:
        • Construct the number N = (the product of all the prime numbers 2 through p) +1.
           Then N has these properties:
 *     • N > p
          [so N cannot be prime, as p is the largest prime number in the alternate universe]
*      • N is not divisible by any of the prime numbers 2 through p
          [so N must be prime, as these are all the possible prime factors of N in the alternate universe]
        • But N cannot be both non-prime and prime at the same time:
   CONTRADICTION!

A final note about this proof: where do we use the Fundamental Theorem of Arithmetic? It is in the step where we prove that N is not divisible by any of the prime numbers 2 through p, and conclude from this that N must be prime. (Some people say that we conclude that either N is prime or N has a prime factor greater than p. The second part is not necessary, but if it makes you feel better, go ahead and put it in. You'll have to patch up the contradiction in the last line of the proof, in that case.)