- #1
kripkrip420
- 54
- 0
Homework Statement
Euclid's proof
Euclid offered the following proof published in his work Elements (Book IX, Proposition 20)[1] and paraphrased here.
Take any finite list of prime numbers p1, p2, ..., pn. It will be shown that some additional prime numbers not in this list exist. Let P be the product of all the prime numbers in the list: P = p1...pn. Let q = P + 1: 1 more than this product. Then, q is either prime or not:
If q is prime then there is at least one more prime than is listed.
If q is not prime then some prime factor p divides q. This factor p is not on our list: if it were, then it would divide P (since P is the product of every number on the list); but as we know, p divides P + 1 = q. Then p would have to divide the difference of the two numbers, which is (P + 1) − P or just 1. But no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list. This means at least one more prime number exists beyond those in the list.
This proves that for any finite list of prime numbers, there is a prime number not on the list. Therefore there must be infinitely many prime numbers.
It is often erroneously reported that Euclid proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes.[2] Although the proof as a whole is not by contradiction, in that it does not begin by assuming that only finitely many primes exist, there is a proof by contradiction within it: that is the proof that none of the initially considered primes can divide the number called q above.
Homework Equations
The Attempt at a Solution
Above is the problem I am facing. There are certain aspects of this proof that I cannot understand. I understand part a of the proof that states if q is prime, then their is one more prime in the list but part b is where it gets tricky. The first thing I don't quite understand is why the prime factor p can only divide q and not P. It states that if p was in the list, then P would be divisible by it. What significance does this have to the proof? I know that if q is not prime, then it must be composite, which means that it must have a prime factor p. But again, the significance of p being able to divide P and therefore existing in the list makes no sense to me. Also, I have never been told before that a prime factor cannot divide 1. This is stated as a contradiction but If you look at the prime number 2, why wouldn't 2 be able to divide 1? Common sense tells me that when you divide 1 by 2, you get 0.5. Have I not just divided 1 by a prime?
Thank you in advance to everyone who helps me on this topic and have a Merry Christmas and a Happy New Year!