1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number Theory-limitation of Pn

  1. Nov 10, 2009 #1
    1. The problem statement, all variables and given/known data

    This is part of Euclid's proof such that he says:
    1)

    [tex]P_{n+1}[/tex] smaller or equal to [tex]P_{1}[/tex][tex]P_{2}[/tex]...[tex]P_{n}[/tex] +1
    Such that p_n is to denote some prime
    I am wondering if anyone could provide me with an elegant prove to the above inequality as i am new to number theory.





    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
    Last edited: Nov 11, 2009
  2. jcsd
  3. Nov 10, 2009 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    That is part of Euclid's proof of what? The "[itex]p_1p_2\cdot\cdot\cdot p_n+ 1[/itex]" reminds me of Euclides proof that there are an infinite number of primes but he never asserts that [itex]p_{n+1}[/itex] is smaller than or equal to that.

    It does, of course, follow from Euclid's proof. Assuming that [itex]p_1[/itex], [itex]p_2[/itex], ..., [itex]p_n[/itex] is a list of all primes less than or equal to [itex]p_n[/itex], [itex]p_1p_2\cdot\cdot\cdot p_n+ 1[/itex] is certainly not divisible by any of [itex]p_1[/itex], [itex]p_2[/itex], ..., [itex]p_n[/itex]. Therefore it is either a prime itself or is divisible by a prime larger than any of [itex]p_1[/itex], [itex]p_2[/itex], ..., [itex]p_n[/itex]. In either case there must be a prime less than or equal to [itex]p_1p_2\cdot\cdot\cdot p_n+ 1[/itex]
     
    Last edited: Nov 12, 2009
  4. Nov 10, 2009 #3
    It is not very elegant but the proof follows from the principles of order on the real number field.

    Considering positive primes: given [tex]p_{1} < p_{2}[/tex], then it follows that [tex]p_{1} < p_{1}^2 < p_{1} \cdot p_{2}[/tex], by inductive reasoning you can prove that [tex]p_{n+1}<p_{n+1} \cdot p_{1} < p_{n+1} \cdot p_{1} \cdot p_{2}[/tex], and so on.
     
  5. Nov 11, 2009 #4

    Gib Z

    User Avatar
    Homework Helper

    Am I understanding the question right? It seems to come quite simply by noting that the primes are larger than 1. We can even omit the equality option of the inequality at a glance.
     
  6. Nov 11, 2009 #5
    Thank you for all your replies (=

    I think i'm able to understand the concept.
    Please tell me your opinions on my proof below.


    Let [tex]P_{1}[/tex][tex]P_{2}[/tex]...[tex]P_{n}[/tex] +1 =N
    Such that N is an element of positive integer.
    Thus, it suggest N is co-prime to [tex]P_{1}[/tex],[tex]P_{2}[/tex], ... ,[tex]P_{n}[/tex]


    Which may be a prime number that is [tex]P_{k}[/tex]
    Such that k is a value larger or equal to n+1


    OR

    It may be a composite number that is larger than [tex]P_{n+1}[/tex] as the smallest possible divisor of N should be [tex]P_{n+1}[/tex] . Noting N is co-prime to [tex]P_{1}[/tex],[tex]P_{2}[/tex], ... ,[tex]P_{n}[/tex] .
     
    Last edited: Nov 11, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number Theory-limitation of Pn
  1. Number Theory (Replies: 1)

  2. Number Theory (Replies: 2)

  3. Number Theory (Replies: 7)

  4. Number of theory (Replies: 1)

Loading...