I am reading some written notes about a proof I do not understand, maybe some informations are missing. The result that has to be proved is the following:

if $p_n$ is the $n$-th prime number, then $p_n \leq 2^{n^2}$.

The proof is by induction on $n$, the case $n=1$ is trivial. So suppose $n>1$. There is $i \in \mathbb{N}$ such that $$ 2^i \leq p_n \leq 2^{i+1}. $$ Then we consider a generic $m \leq p_n$, where $m=p_1^{\alpha_1} \cdots p_n^{\alpha_n} $ with $a_j \in \{0,1,\dots i\}$. Then (probably using the fact that there are $p_n$ naturals less or equal than $p_n$ and that $m$ is determined by $a_j$'s ??????) we get $$ p_n \leq (i+1)^n $$...


How do we get this last inequality?

  • $\begingroup$ Looks confusing to me indeed. $\endgroup$ – Peter Franek Jul 17 '14 at 20:04

What you write in parentheses is exactly the idea. Consider the set $S$ of natural numbers that can be written in the form $p_1^{\alpha_1}\cdots p_n^{\alpha_n}$ with each $\alpha_j \in \{0,1,\ldots,i\}$. Since each such expression is unique, this set is in bijection with the set of $n$-tuples $(\alpha_1,\ldots,\alpha_n)$ with each $\alpha_j \in \{0,1,\ldots,i\}$, of which there are $(i+1)^n$ elements. That is, $S$ has $(i+1)^n$ elements. However, every $m\leq p_n$ is in this set, as every $m \leq p_n$ can be written as a product of the primes $p_1,\ldots,p_n$. So $\{1,2,\ldots,p_n\} \subseteq S$, from which the inequality follows.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.