Euclid's Proof for Prime Numbers

[kripkrip420]

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!

 

[hgfalling]

"x divides y" means "y divided by x is an integer." So no prime number divides 1.

 

[kripkrip420]

So your telling me that the resulting number must be an integer and not a fraction? Also, why can't p divide P and only q?

 

[kripkrip420]

Oh and why must p divide the difference between P and Q?

 

[hgfalling]

Well, suppose p divides both P and q.

Then there is some integer m such that mp=P and some integer n such that np = q, right?

But now consider the difference between P and q, P - q. By the above we know that this is also equal to mp - np, or (m-n)p. Since m and n are integers, their difference is an integer. Hence p has to divide the difference between them.

But in Euclid's proof, q is P+1. So if p divides P and q, then p has to divide their difference. But that's one, and so that's impossible. Hence p doesn't divide both P and q.

 

[kripkrip420]

Thank you very much! All of this makes sense except for one bit. Why MUST p divide the difference of two integers? Also, 1 is divisible by a number but it yields a fraction. Why must the result be an integer?

Again, thank you so much for your help. I understand the proof, I just don't understand why certain things exist the way they do.

 

[hgfalling]

The reason we don't allow fractions here is just because when we are talking about prime numbers, we are only concerned with integers, because that's what makes a number "prime." I mean, if we allowed fractions, then every number would be composite, and in an infinite number of ways. That just wouldn't be very interesting.

It's easy to see why in order for p to divide both P and q, it has to divide P-q.

Suppose p divides q, ie q = mp, m an integer. Then

P = q + P - q

Then suppose that p does NOT divide P-q. Then we have:

P-q = np + r where 0 < r < p and n is an integer.

So P = mp + np + r = (m+n)p + r.

So p doesn't divide P. You can easily show by the same argument that if it does divide P-q, then it divides both.

 

[kripkrip420]

I'm sorry but now you've confused me further. What does q/p have anything to do with P=q+P-q?

 

[kripkrip420]

Ok. I understand everything now. Can you just prove to me that if two numbers, say a and b, have the same factor, then their difference is indeed also divisible by that factor.

Thank you so much for your help!

 

[hgfalling]

Let a = mk and b=nk, where n and m are integers, and k is some prime factor of a and b.

Claim: (a-b) is divisible by k.

(a-b) = (mk-nk) = k(m-n)

m-n is an integer because m and n are integers, hence (a-b) is divisible by k.

 

[kripkrip420]

Yes, sorry, I figured this out earlier. Sorry I did not post to say so. I appreciate the time you have taken to explain this to me. Please know that you have helped someone understand even more just how beatiful math can be. Again, I thank you for all your help!