# Euclid Proof of Infinite Primes

1. May 25, 2009

### 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.

2. May 25, 2009

### 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?

3. May 25, 2009

### Pupil

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.

4. May 25, 2009

### 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?

5. May 25, 2009

### HallsofIvy

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

6. May 26, 2009

### CRGreathouse

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

7. May 26, 2009

### 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.

8. May 26, 2009

### qntty

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$$