# Euclid's theorem and primes numbers

• Oct 10th 2006, 08:02 AM
jedoob
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.
• Oct 10th 2006, 08:33 AM
ThePerfectHacker
Quote:

Originally Posted by jedoob
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.