This is a question in a book in Portuguese.

Let $p_n$ be the $n$-th prime number. Show that $p_n\leq 2^{2^{n-2}}+1$.

The book gives a hint: use the facts that $\gcd(F_i,F_j)=1$, if $i\neq j$, $2$ is not a divisor of $F_i$ and $F_5$ is not prime, where $F_i$ is the $i$-th Fermat number.

I was unable to use the suggestion. I can't see how use that $F_5$ is not prime. I tried to use the fact that a divisor of a Fermat number has the form $4m+1$, but I get nothing.

I would appreciate any help.


Let $F_k=2^{2^k}+1$. To make my work a little harder, I will start with $p_0=2$. So we have to produce $n+1$ primes that are $\le F_{n-2}$. This is easy to do for small $n$.

I will assume that you have proved that for $k=0$, $1$, and so on up to $n-2$, the $F_k$ are pairwise relatively prime.

For each of these, let $q_k$ be (say) the smallest prime factor of $F_k$. Since the $F_i$ are pairwise relatively prime, that gives us $n-1$ primes that are $\le F_{n-2}$.

In addition to the $q_k$, there is of course the prime $2$, which is not one of the factors of any $F_k$, and the extra prime we get because $F_5$ is not prime. (Actually, we need something a little stronger, that $F_5$ is not a prime power).

But we don't really have to worry about $F_5$ at all. For apart from the prime $3$, all primes that divide $F_k$ must be of shape $4t+1$. So the primes $7$ and $11$, added to $2$ and the $q_k$, get the count high enough.


Hint $\ $ A variant of Euclid's classical proof is that one may construct an infinite sequence of primes from any infinite sequence of coprimes, e.g. give an increasing sequence of naturals $\rm\:f_n > 1\:$ that are pairwise coprime, i.e. $\rm\:(f_i,f_j) = 1\:$ for $\rm\:i\ne j,\:$ then choosing $\rm\:p_i\:$ to be a prime factor of $\rm\:f_i\:$ yields an infinite sequence of primes, since the $\rm\:p_i\:$ are distinct: $\rm\:p_i\ne p_j,\:$ being factors of coprimes $\rm\:f_i,\, f_j\:$.

Therefore $\rm\:f_n \ge \:$ the $\rm n$'th prime, since there are at least $\rm\:n\:$ primes smaller than it, viz. the primes $\rm\:p_1,\ldots, p_n,\:$ where $\rm\:p_k|\:f_{\,k}\:\Rightarrow\:p_k\le f_{\,k} \le f_n\:$ by $\rm\:k\le n,\:$ since $\rm\:f_n\:$ is increasing.

To complete the proof of your problem, you need only show there are two more such primes when $\rm\:f_n = F_n,\:$ which the hint reveals, viz. the prime $2$ and the pair of primes from $\rm\:F_5$.

Remark $\ $ Goldbach used the coprimality of the Fermat numbers in this way to prove that there are infinitely many primes (in a letter to Euler in 1730, see Ribenboim's The New Book of Prime Number Records, p. 4).


First note that $p_1 = 2 < 2^{\sqrt{2}} + 1$, $p_2 = 3 \leq 2^{2^0} + 1$. Now use induction.

From Bertrand's postulate, we know that $p_m < p_{m+1} \leq 2p_{m}-2$.

Hence, $p_{m+1} \leq 2 \left( 2^{2^{m-2}} +1\right) - 2 = 2^{2^{m-2}+1} \leq 2^{2^{m-1}}+1$


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.