Uncovering the Mystery of Euclid's Proof of Infinite Primes

[cragar]

I am trying to understand Euclid's proof of infinite primes. So let's say we have a finite list of primes n1, n2 ... N where N is the largest prime .
Then we take the product of all of these prime numbers, and we will call it Q .
Then we add 1 to it . so this number is either prime or not . If it is prime then we have one more that isn't in our list. But then if it isn't prime, then some larger prime will divide it .
But why can't the number that divides it be even why does it have to be a prime number that can divide it? It is probably simple but I don't see it .

 

[jhae2.718]

The Fundamental Theorem of Arithmetic states that all integers greater than 1 can be written as a unique product of prime factors.

Since no primes divide Q, it follows that Q must be prime.

 

[Sourabh N]

I am trying to understand Euclid's proof of infinite primes. So let's say we have a finite list of primes n1, n2 ... N where N is the largest prime .
Then we take the product of all of these prime numbers, and we will call it Q .
Then we add 1 to it . so this number is either prime or not . If it is prime then we have one more that isn't in our list. But then if it isn't prime, then some larger prime will divide it .
But why can't the number that divides it be even why does it have to be a prime number that can divide it? It is probably simple but I don't see it .

Because n1 (or n2, depending how you start) = 2. So n1*n2*...*N is an even number. Add 1 to that, you have an odd number.

 

[cragar]

thanks for your responses. If we divide our list by any numbers in the list we will have a remainder of 1 , So does this means that Q+1 is a prime number or divisible by a larger prime number because no other division would leave us with a remainder of 1?

 

[gb7nash]

Take a look at the proof I listed in this thread. Copy paste isn't working:

https://www.physicsforums.com/showthread.php?p=3229471#post3229471

 

[uart]

thanks for your responses. If we divide our list by any numbers in the list we will have a remainder of 1 , So does this means that Q+1 is a prime number or divisible by a larger prime number because no other division would leave us with a remainder of 1?

Hi Cragar. Every integer >1 must have at least one prime factor. If the number itself is a prime then that's the only factor (apart from 1), if it's a non-prime then it's got at least two prime factors. So they all have at least one prime factor!

So quite simply since our new number "Q+1" contains at least one prime factor (as do all numbers >1), and since none of the primes on our list are candidates, then this implies that there must be at least one more prime (\leq \, Q+1) that is not already on our list. In effect this mean that no matter how extensive is our list we can always prove that it's not complete.

 

[cragar]

thanks everyone for your replies and uart that really cleared it up.

 

[DarthPickley]

you have to prove that ( a*b + 1 ) is not divisible by a or b, and the same for like (a*b*c*d*e*f*g + 1) is not divisible by a,b,c,d,e,f,g. (and of course they are not equal to one)
this is done really easily if you say that a*(...) ≡ 0 (mod a), then a*(...) + 1 ≡ 0+1 ≡ 1 (mod a). so if it is not 0 (mod a), then it is not divisible by a, so it is not divisible by any of the others. this is sort of obvious, but it might not be that obvious at first...

 

[cragar]

okay that helps too, thanks