Results 1 to 8 of 8
Like Tree1Thanks
  • 1 Post By Plato

Math Help - Euclid's proof of infinitude of primes...

  1. #1
    Newbie
    Joined
    Aug 2013
    From
    Canada
    Posts
    9

    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 !
    Last edited by philomath; August 9th 2013 at 06:33 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Feb 2010
    From
    in the 4th dimension....
    Posts
    122
    Thanks
    9

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

    Quote Originally Posted by philomath View Post
    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 m=p_{1}p_{2}...p_{n}+1
    hence, you will always get the remainder 1.If,say,the random q=p_{5},and we divide \frac{m}{p_{5}}= p_{1}p_{2}...p_{n}(without p_{5}) +(1/p_{5}) or 1 is the remainder as it does not fully go with p_{5}.

    Quote Originally Posted by philomath View Post
    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.

    Quote Originally Posted by philomath View Post
    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 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 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 2,3,5 and see what happens....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2013
    From
    Canada
    Posts
    9

    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)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,661
    Thanks
    1616
    Awards
    1

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

    Quote Originally Posted by philomath View Post
    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: p_1,~p_2,\cdots,~p_n~. Now if q is a prime then (\exists k)[1\le k\le n~\&~q=p_k].

    Thus q is in the product.
    Thanks from ChessTal
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2013
    From
    Canada
    Posts
    9

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

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

    Thus q is in the product.
    I have no idea what is the inversed E symbol...^^could you reformulate ? Thank you
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Feb 2010
    From
    in the 4th dimension....
    Posts
    122
    Thanks
    9

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

    Quote 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"

    please read the proof carefully (and its very simple)...

    the \exists stands for 'there exists'.
    Plato has just written that the prime q is within primes p_{1} and p_{n}, and is well inside your list of primes.I think its now very understandable.
    Last edited by earthboy; August 9th 2013 at 08:08 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,661
    Thanks
    1616
    Awards
    1

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

    Quote Originally Posted by philomath View Post
    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.
    If you ask an advanced question, expect to get an advanced answer.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Aug 2013
    From
    Canada
    Posts
    9

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

    Yes, you are right. It's just I barelly begun reading about it, and the author didn't begin completely the subject.(I'm only in the intro) Anyway, thank you for your answer
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid Division Lemma proof.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 11th 2012, 03:35 PM
  2. Euclid's Lemma Proof by Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 7th 2011, 01:25 AM
  3. Simple proof for the infinitude of surds
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 7th 2009, 06:41 AM
  4. Complexity based proof of infinitude of Primes
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 10th 2007, 01:29 PM
  5. Euclid's theorem and primes numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 10th 2006, 07:33 AM

Search Tags


/mathhelpforum @mathhelpforum