# Thread: Euclid's proof of infinitude of primes...

1. ## Euclid's proof of infinitude of primes...

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 !

2. ## Re: Euclid's proof of infinitude of primes...

Originally Posted by philomath
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.).
No.You wont be able to completely divide m by q, because remember $\displaystyle m=p_{1}p_{2}...p_{n}+1$
hence, you will always get the remainder 1.If,say,the random $\displaystyle q=p_{5}$,and we divide $\displaystyle \frac{m}{p_{5}}= p_{1}p_{2}...p_{n}$(without $\displaystyle p_{5}$)$\displaystyle +(1/p_{5})$ or 1 is the remainder as it does not fully go with $\displaystyle p_{5}$.

Originally Posted by philomath
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...)
It comes because of the above reason.

Originally Posted by philomath
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 ???
You have already supposed that $\displaystyle p_{1},p_{2},...,p_{n}$are your only primes, and you have no more of them.But you have actually built yourself a new prime number $\displaystyle p_{1}p_{2}...p_{n}+1$ , because it has all the properties of prime(isn't divisible by anything other than 1 or itself), and it ought to be on your list.So you have one more prime..and the same reason could be applied to get more and more of such primes...to infinity.

I suggest to take and work with some examples like make your list of primes only $\displaystyle 2,3,5$ and see what happens....

3. ## Re: Euclid's proof of infinitude of primes...

Sorry, but I asked on another forum and the other guy says that q is NOT on our list.... It seems a contradiction to me....(between you two)

4. ## Re: Euclid's proof of infinitude of primes...

Originally Posted by philomath
Sorry, but I asked on another forum and the other guy says that q is NOT on our list.... It seems a contradiction to me....(between you two)
Well, the other guy is mistaken.
The proof assumes that there are only finitely many primes.
Therefore, we can list them: $\displaystyle p_1,~p_2,\cdots,~p_n~.$ Now if $\displaystyle q$ is a prime then $\displaystyle (\exists k)[1\le k\le n~\&~q=p_k]$.

Thus $\displaystyle q$ is in the product.

5. ## Re: Euclid's proof of infinitude of primes...

Originally Posted by Plato
Well, the other guy is mistaken.
The proof assumes that there are only finitely many primes.
Therefore, we can list them: $\displaystyle p_1,~p_2,\cdots,~p_n~.$ Now if $\displaystyle q$ is a prime then $\displaystyle (\exists k)[1\le k\le n~\&~q=p_k]$.

Thus $\displaystyle q$ is in the product.
I have no idea what is the inversed E symbol...^^could you reformulate ? Thank you

6. ## Re: Euclid's proof of infinitude of primes...

Originally Posted by philomath
Sorry, but I asked on another forum and the other guy says that q is NOT on our list.... It seems a contradiction to me....(between you two)
it is clearly written in your attachment :"let q be one of the primes in this product"

the $\displaystyle \exists$ stands for 'there exists'.
Plato has just written that the prime q is within primes $\displaystyle p_{1}$ and $\displaystyle p_{n}$, and is well inside your list of primes.I think its now very understandable.

7. ## Re: Euclid's proof of infinitude of primes...

Originally Posted by philomath
I have no idea what is the inversed E symbol.
It would behoove you to learn common mathematical & logical symbols if you continue to read advanced proofs.