11
$\begingroup$

Let $p_n$ be the $n_{th}$ prime (e.g. $p_1 = 2$; $p_2 = 3$; $p_3 = 5$). Show that $p_n \leq 2^{2^n}$ for all $n$.

I don't see how I can approximate the value of $p_n$. Do I need something like prime number theorem? But the course didn't even teach that yet.

  • 0
    @Thijs: Indeed; which is why I upvoted your answer. (-:2011-09-18

3 Answers 3

23

The idea is that you use induction, and that you expand on Euclid's argument that there are infinitely many primes to show that $p_n$ is bounded above by $2^{2^n}$.

Suppose $p_i \leq 2^{2^i}$ for all $i \leq n$. Now $p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$ is not divisible by any of the primes $p_1, \ldots, p_n$, so

$p_{n+1} \leq \prod_{i=1}^n \ p_i + 1$

Substituting the earlier bounds on $p_i$ and using $\sum_{i=1}^n 2^i = 2^{n+1} - 2$, we get

$p_{n+1} \leq \left(\prod_{i=1}^n \ 2^{2^i}\right) + 1 = \left(2^{\sum_{i=1}^n 2^i}\right) + 1 = 2^{2^{n+1} - 2} + 1 \leq 2^{2^{n+1}}$

16

It is enough to prove that for any positive integer $n$, there are at least $n$ primes that are $\le 2^{2^n}$. We will show that in fact $2^{2^n}-1$ always has at least $n$ distinct prime divisors. (All of these are necessarily $<2^{2^n}$.)

Suppose we know that $2^{2^k}-1$ has at least $k$ distinct prime divisors. Then we must show that $2^{2^{k+1}}-1$ has at least $k+1$ distinct prime divisors.

Note that $2^{2^{k+1}}-1=(2^{2^k}-1)(2^{2^k}+1).$ The numbers $2^{2^k}-1$ and $2^{2^k}+1$ are relatively prime. This is because any number that divides both of them must divide their difference, which is $2$. But each of $2^{2^k}-1$ and $2^{2^k}+1$ is odd, so the greatest integer that divides both of them cannot be $2$, and therefore must be $1$.

Thus the prime divisors of $2^{2^{k+1}}-1$ are the prime divisors of $2^{2^k}-1$ (of which there are at least $k$), together with the prime divisors of $2^{2^k}+1$ (of which there is at least $1$), for a total of at least $k+1$.

Comment: The above argument also tells us that for any positive integer $n$, there are at least $n$ primes. This gives us a proof of the infinitude of the primes which is a little different from the usual "Euclid" proof.

  • 2
    (+1): very nice example how to make things simple - I think, the "least effort solution" :-)2011-09-19
1

Here we look at a smaller, and as I feel, more convenient bound:

Assume each prime would be the double of the previous, we had, beginning with the first prime q=2 the sequence $ \small q, 2q, 4q, 8q, \ldots 2^n q , \ldots...$ and the n'th prime were bounded by $ \small q2^n $ which is much smaller than the given $ \small 2^{2^n} $ . Now if we recall that between n and 2n there is always a prime, thus the distance to the next is even smaller than n , then this is sufficient for the proof in general and we need only look at the initial cases for possible exceptions.

  • 0
    @Thijs: Well, I was thinking just in that path of an exercise for proofs (and Bertrand's postulate seemed to me to be *the* elementary knowledge here). But possibly I'm too far away from the actual courses to have an appropriate intuition. So if I was obfuscating here, I'll apologize to the OP...2011-09-19