Results 1 to 2 of 2

Math Help - Euclid's theorem and primes numbers

  1. #1
    Junior Member
    Joined
    Feb 2006
    Posts
    32

    Euclid's theorem and primes numbers

    Hi,

    How do I prove that if Pn is the n-th prime, then Pn < 2^(2^n) - using Euclid's theorem?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by jedoob View Post
    Hi,

    How do I prove that if Pn is the n-th prime, then Pn < 2^(2^n) - using Euclid's theorem?

    Thanks.
    Ah! famous theorem.

    In fact you can even make a stronger statement that,
    p_n<= 2^(2^{n-1})

    We note that by it works for n=1
    2=P_1<=2^(2^{0}}=2

    We assume that is works for first k primes,
    Thus, by Euclid's nice argument we have,
    p_{k+1}<=p_1p_2....p_k+1
    But for each prime on right hand we have,
    p_1<=2^(2^0)
    p_2<=2^(2^1)
    p_3<=2^(2^2)
    .....
    p_k<=2^(2^{k-1}}
    Thus, (multiply out exponents is adding exponents)
    p_{k+1}<=2^(1+2+2^2+2^3+...2^{k-1})+1
    Thus, (recognize the geometric series),
    p_{k+1}<=2^{2^k-1}+1
    But,
    1<=2^(2^k-1)
    Thus,
    p_{k+1}<=2^{2^k-1}+2^{2^k-1}
    But,
    2^{2^k-1}+2^{2^k-1}=2*2^{2^k-1}=2^{2^k}
    Thus,
    p_{k+1}<=2^{2^k}
    Induction complete.
    Q.E.D.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid's Exterior Angle Theorem (EEAT)
    Posted in the Geometry Forum
    Replies: 2
    Last Post: December 1st 2010, 09:05 AM
  2. Euclid's "perfect numbers theorem"
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 1st 2010, 01:48 AM
  3. Replies: 1
    Last Post: April 24th 2010, 04:51 PM
  4. Replies: 0
    Last Post: May 28th 2009, 09:07 AM
  5. Euclid's Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 2nd 2008, 11:52 AM

Search Tags


/mathhelpforum @mathhelpforum