Euclid's proof of infinitude of primes

[chemistry1]

Hi, I'm new into the domain of proofs, and I'm reading How to prove it - A structured approach.




I'm having a problem with the last paragraph... If m is a product of primes, and q is one of those primes taken randomly, then we should be able to divide m by q to obtain the rest of the primes(p1,p2,etc.). But we established earlier that we CANNOT divide evenly, because we will have a remainder of one (By the way, I wonder where it comes from...)So now, I understand that this is a contradiction, but I'm not sure of following the ''we have a contradiction with the assumption that this list included all prime numbers." I'm not having the same conclusion about it, how does this prove that the list doesn't have ALL primes, even if we can't divide evenly? If it really contained all the primes, should we be supposed to divide it without a remainder, is it because primes are missing that it won't divide ? Thank you for your help !

 

[Number Nine]

But we established earlier that we CANNOT divide evenly

No, it was established that $m = p_1p_2...p_n + 1$ is not divisible by any $p_i$, which, by assumption, include all of the prime numbers. But $m$ must be divisible by some prime number (by the fundamental theorem of arithmetic), so it follows that there is some prime $q$ dividing $m$ that isn't on our list. By contradiction, there are not only finitely many prime numbers.

 

[chemistry1]

Ah okkkkkkkkkk, now I understand.lol fail from me, I should have thought more about it. There is just one thing I don't follow, you said that the theorem of arithmetic says that m must be divisible by some prime number. If it can be divide by "q", but not by any p1,p2,etc. How does it make any sense ? (Or I didn't understand it correctly, who knows.) Thank you for your responce !

 

[ateixeira]

This is the gist of the argument:

1- The result of the multiplication of integers is an integer. Hence p_1p_2...p_n is an integer
2- The result of the addition of integers is an integer. Hence p_1p_2...p_n+1 is an integer
3- The fundamentel theorem of arithmetics states that all natural numbers different than 1 are divisible by a prime number
4- Hence m is an integer is divisible by a prime number
5- You assume that the prime numbers are finite in extension
6- If the prime numbers are finite in extension m (the number that you constructed which is an integer) can't be divided by any of the p_i of you initial list of prime numbers
7.1- Hence m itself must be a prime. But m wasn't in your initial list of "all primes that exist". Which ois absurd!
7.2 There exists another prime p_{n+1} (that wasn't in your initial list of "all primes that exist") that divides m. Absurd!

PS: Do you understand why this argument only works with m=p_1p_2...p_n+1 but doesn't work if you define m=p_1p_2...p_n+2 (or + any other positive integer different than 1)?