Hi,

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

Thanks.

Printable View

- October 10th 2006, 07:02 AMjedoobEuclid'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. - October 10th 2006, 07:33 AMThePerfectHacker
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.