Reply
Sun 18 Sep, 2005 03:55 pm
Hi all! I'm supposed to use Euclid's proof that there are infinitely many primes to show that the nth prime p_n does not exceed 2^(2^(n-1)) whenever n is a positive integer. Conclude that when n is a positive integer, there are at least n+1 primes less than 2^(2^n).
Euclid proved that p_1 * p_2 * p_3 * ... * p_n + 1 must be prime or the product of primes greater than p_n.
Well, if p_1 <= 2^(2^0) and p_2 <= 2^(2^1) and ... p_n <= 2^(2^(n-1)), can you show that p_1 * p_2 * ... * p_n + 1 <= 2^(2^n)?
Think about what you do to the exponents when you multiply powers of two. Think also about the sum of the first n powers of two.