Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euclid's Proof

  1. Feb 18, 2010 #1
    Hi, I am having trouble understanding this proof.


    Statement

    If pn is the nth prime number, then pn [tex]\leq[/tex] 22n-1


    Proof:


    Let us proceed by induction on n, the asserted inequality being clearly true when n=1. As the hypothesis of the induction, we assume n>1 and the result holds for all integers up to n.

    Then

    pn+1 [tex]\leq[/tex] p1p2...pn + 1

    pn+1 [tex]\leq[/tex] 2.22...22n-1 + 1 = 21 + 2 + 22+ ...+ 2n-1

    Recalling the indentity 1 + 2 +22+ ...+2n-1=2n-1

    Hence

    pn+1 [tex]\leq[/tex] 22n-1+1

    But 1 [tex]\leq[/tex] 22n-1 for all n; whence

    pn+1 [tex]\leq[/tex]22n-1+22n-1
    =2.22n-1
    =22n
    completing the induction step, and the argument.



    What I don't understand is why the proof uses p1, p2, etc as powers of two. What is the nature of the pn? Are they prime or what? Why use powers?
     
  2. jcsd
  3. Feb 18, 2010 #2
    In the proof , it is not that p1 , p2 , p3 have been replaced by powers of 2 . All that it is saying is that :

    p1.p2.p3.p4.....pn < 2 . (2^2) . (2^4) .... ( 2 ^ (2^n - 1 ) ).

    This is because it is assuming the theorem to be true for p1 , p2 .. upto pn .
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Euclid's Proof
  1. A proof (Replies: 1)

  2. Proof needed (Replies: 1)

  3. Help with a proof. (Replies: 5)

  4. Inverse Proof! (Replies: 2)

Loading...