Euclid Proof of Infinite Primes

[Pupil]

Near the end of Euclid's proof he says that if you multiply all our known primes from 2 to Pn and then add 1 to it, the number isn't divisible by any of our primes up to Pn, because it leaves the remainder 1. Why is that? How does he know that it will always leave the remainder 1? Couldn't adding 1 just make a slightly larger number that has a factor that might be 2 or Pn? If someone can set my stoopid brain straight I'd be very happy. Thanks.

 

[matt grime]

We have that 2,..,p_n is a supposed list of all primes and we have constructed

2*3*..*p_n+1

By construction it is one more than a multiple of any known prime (i.e. 2,..,p_n).

Or, let me put it this way, I have something that is a multiple of 2, and I add one to it. Is the result a multiple of 2?

 

[Pupil]

We have that 2,..,p_n is a supposed list of all primes and we have constructed

2*3*..*p_n+1

By construction it is one more than a multiple of any known prime (i.e. 2,..,p_n).

Or, let me put it this way, I have something that is a multiple of 2, and I add one to it. Is the result a multiple of 2?

No, as far as I can tell by doing a few examples in my head. I can maybe see how 2n + 1 never yields a multiple of 2 since 2n is always even, and adding 1 makes it odd, thereby making it indivisible by 2. Your multiple of 2 example is really simple, so I can see easily how to prove that result, but I don't see how it is known that multiplying all the primes and adding 1 constructs a number such that it isn't a multiple of any known prime.

 

[Pupil]

To kind of clarify the problem I'm having: how do we know kn+1 is not divisible by k or any of the factors that make up k?

 

[HallsofIvy]

Because if you divide kn+ 1 by k you get a quotient of n with remainder 1.

 

[CRGreathouse]

To kind of clarify the problem I'm having: how do we know kn+1 is not divisible by k or any of the factors that make up k?

Because kn is divisible by k (leaving a remainder of 0), so one more than that would leave a remainder of 1.

 

[alligatorman]

$$\frac{kn+1}{k}=n+\frac{1}{k},$$

where n is an integer.

If p is a factor of k, then

$$\frac{kn+1}{p}=n'+\frac{1}{k},$$ where n' is an integer.

 

[qntty]

To kind of clarify the problem I'm having: how do we know kn+1 is not divisible by k or any of the factors that make up k?

perhaps it would be easier to see it this way: if you cycle through the integers, a multiple of k will appear ever k integers starting with 0 then k then 2k, 3k, etc. If P is the product of all known primes, then it is divisible by every prime, so in order to get a number that's divisible by any factor of P (ie any prime) you need to add at least 2 (the smallest prime) but 1>2 so $$2\not| P$$