Thursday, August 25, 2016

elementary number theory - Proof of infinitely many primes, clarification



Proof:
The proof is by contradiction.
Suppose there are only finitely many primes.
Let the complete list be p1,p2,,pn.
Let N=p1p2pn+1.
According to the Fundamental Theorem of Arithmetic, N must be divisible by some prime.
This must be one of the primes in our list. Say pkN.
But pkp1pn, so pk(Np1pn)=1
Hence contradiction.




I don't see how this proof works. I understand that N isn't necessarily prime, but I don't understand how it apparently must show that some primes weren't in our list. A number could be made of different powers of the given primes right?



Someone please explain.


Answer



Suppose that there are only n primes. Let p1,p2,p3,,pn be all the primes in the world. Let N be the product of all these primes plus 1, i.e. N=p1p2pn+1. We know that N must be a product of primes. But the only primes in the world are p1,p2,,pn. So one of these must be a factor of N. Since it doesn't matter which, let's say p1 is a factor of N. Then we use
N=p1p2pn+1
to find that

Np1p2pn=1
But p1 divides the left side of the equality since p1 is a factor of N (from above) and it divides p1p2pn because it's part of the product.



But since it divides the left side it must divide the right side of the equality. But that means p1 divides 1. But that can't happen because p1 has to be at least as big as 2 - the smallest prime there is - and no number except 1 and 1 divide 1. Therefore, we have a contradiction. This means our assumption - that there are only n primes, is wrong.



What we have done is used our primes p1,p2,,pn to make a number which needs a new prime not among the list p1,p2,,pn. So for any n primes you have, you can always make a number forcing you to need at least one more prime which lets you make another such number and so forth. So of course there are infinitely many primes.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...