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.


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


    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.


    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


    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
    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 .
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook