4
$\begingroup$

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.

3 Answers 3

6

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.

2

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).

1

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$