14
$\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.

$\endgroup$
4
  • 12
    $\begingroup$ You could use the fact that if $p_1,\ldots,p_n$ are the first $n$ primes, then the $(n+1)$st prime is less than or equal to $p_1\cdots p_n + 1$ (Euclid's argument for the infinitude of primes). So, inductively, $p_{n+1}\leq 2^{2^1}\times\cdots\times 2^{2^n}+1 = 2^{2^1+\cdots+2^n}+1$. $\endgroup$ Sep 18, 2011 at 23:32
  • 3
    $\begingroup$ It's worth pointing out that this is an incredibly crude bound. The prime number theorem states that $p_n$ is in fact approximately $n \log n \ll n^2 \ll 2^n \ll 2^{2^n}$. $\endgroup$ Sep 18, 2011 at 23:44
  • $\begingroup$ @Arturo: Typing my answer took longer than you typing you comment, but the idea is of course exactly the same as yours. $\endgroup$
    – TMM
    Sep 18, 2011 at 23:46
  • $\begingroup$ @Thijs: Indeed; which is why I upvoted your answer. (-: $\endgroup$ Sep 18, 2011 at 23:50

3 Answers 3

28
$\begingroup$

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}}$$

$\endgroup$
19
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ (+1): very nice example how to make things simple - I think, the "least effort solution" :-) $\endgroup$ Sep 19, 2011 at 6:36
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Gottfried: The question seems more aimed at getting the student familiar with proof techniques (induction) than proving a sharp bound on the size of the $n$th prime. But indeed, one can improve the bound quite a bit ;-) $\endgroup$
    – TMM
    Sep 19, 2011 at 1:19
  • $\begingroup$ @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... $\endgroup$ Sep 19, 2011 at 6:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .