Help with Euclid's Primes Proof?

Question

I'm studying for math team next year, and we're currently on Euclid's Infinite Primes Proof.
Apparently, one way to do it is by subtraction, but this way makes no sense to me. Here's what my book says:
"There are either finitely or infinitely many primes. Assume that there are only finitely many and multiply all of them together to form a very large integer n = 2x3x5x7x... Now, since n+1 is greater than any of the factors of n it cannot be prime, so one of the factors of n also has to be a factor of n+1. But, if this were so, then (n+1)-n=1 would also have the same factor. This is a contradiction, so we conclude that our assumption of finitely many primes is false".
I understand perfectly, up to the "But, if this were so" sentence. Why would the difference have the same factor? And how is this a contradiction? Please use as much detail as you possibly can.
The way I understand it is that there are infinitely many primes because (n+1)/a prime in n would come up with a remainder of 1, which is not an integer and doesn't work. Is this a valid way to do this proof? I know there are many ways...
Thank you!

? · Accepted Answer

Suppose n+1 had a prime factor p, and write (n+1) = pr for an integer r. Similarly write n = ps for an integer s. Then (n+1) - n = pr - ps = p(r-s) = 1, so 1 would have p as a prime factor--which makes no sense. [The left side would have to be >= 2, for instance.] Their explanation could have been clearer.

cryptogramcorner · Answer

Because n + 1 can't be prime, it must be able to be factored into the product of primes. If we call
one of those primes k, then we must be able factor n + 1 into k(C1), when C1 is just the product
of (n+1)'s remaining factors


Because n is, by our assumption, the production of all primes the it can also be factored into
the product of k and some integer C2.   n = k(C2), where C2 is the product of n's remaining factors.


So we can write  (n + 1) - n  as

k(C1) - k(C2)   or

k (C1-C2)

but since (n+1) - n = 1  that means that

k (C1-C2) = 1

Since C1 and C2 are integers, and k > 1, this is impossible and we have our contradiction.  



The other way I've seen this explained is that since (n+1) can't be prime according to the
assumption, that means that at least one of the finite number of primes must divide into it.
Then you show that no matter which one you try, you are going to get a remainder of 1, which means that you can't find any prime factors and you have a contradiction.

satterly · Answer

One wonders if the priority is in how they're provided or of their essence. math_kp is appropriate that the assertion isn't that N+a million is best, besides the reality that the N+a million (or N-a million for that rely) which at the instant are not best are sparse. observe that maximum proofs that we see as we communicate have imposed the logical self-discipline it incredibly is popular as we communicate and additionally take the "shortest distance to the answer" suggestions-set. i do no longer comprehend that that makes the data clean. actual the reason of the originator is often lost yet especially situations the respond seems much less confusing(evaluate the progression of Weierstrass polynomials to coach denseness interior the non-end purposes to a topological suggestions-set). interior the tip, nonetheless, as Bertrand Russell might say: Is there something that is stated with actuality?

Trending News

Help with Euclid's Primes Proof?

3 Answers