Exercise 1.3.48* (There are infinitely many primes, second proof.)

Question

Prove that there are infinitely many primes by considering the sequence $2^{2^1}+ 1,2^{2^2} + 1,2^{2^3} +1, 2^{2^4} + 1,\ldots$

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}}

\begin{proof} Write $F_n = 2^{2^n} +1$ the $n$-th Fermat number, for $n\geq 0$.

By exercise 1.2.49 we know that $\mathrm{gcd}(F_n,F_m) = 1$ if $n 
e m$.

Define $p_n$ as the least prime factor of $F_n$. For instance $p_0 = 3, p_1 = 5, p_2 = 17$ and $p_5 = 641$ (see Ex. 1.3.43).

If $n 
e m$, then $p_n 
e p_m$, because $\mathrm{gcd}(F_n,F_m) = 1$.

Therefore the set $\{p_0, p_1,p_2,\ldots,p_n,\ldots\}$ of prime numbers is infinite. This shows that there are infinitely many primes.

\bigskip
More formally, write $\mathbb{P} = \{2,3,5,7,\ldots\}$ the set of prime numbers. The map
$$
\varphi
\left\{
\begin{array}{ccl}
\N & 	o & \mathbb{P}\
n & \mapsto &p_n  = \min\{p \in \mathbb{P},\  p \mid F_n\}
\end{array}
ight.
$$
is an injection. Therefore $\mathbb{P}$ is infinite.
\end{proof}

Exercise 1.3.48* (There are infinitely many primes, second proof.)

Answers

Comments

Exercise 1.3.48* (There are infinitely many primes, second proof.)

Answers

Comments

Add answer