Exercise 1.3.43 ($F_5$ is composite.)

Question

The numbers $F_n = 2^{2^n} + 1$ in the preceding problem are called the {\bf Fermat numbers}, after Pierre de Fermat who thought they might all be primes. Show that $F_5$ is composite by verifying that
$$(2^9+2^7+1)(2^{23} - 2^{21} + 2^{19} - 2^{17} + 2^{14} - 2^9 - 2^7 + 1) = 2^{32} +1.$$

(It is not hard to show that $F_n$ is prime for $n = 0, 1,\ldots,4$; these are the only $n$ for which $F_n$ is known to be prime. It is now known that $F_n$ is composite for $n = 5, 6, \ldots, 21$. It is conjectured that only finitely many Fermat numbers are prime.)
}

Richard Ganaye · Accepted Answer

Let $N =(2^9+2^7+1)(2^{23} - 2^{21} + 2^{19} - 2^{17} + 2^{14} - 2^9 - 2^7 + 1)$.

Then, using $2^k + 2^k - 2^{k+1} = 0$,
\begin{align*}
N = & 2^{32} - 2^{30} + 2^{28} - 2^{26} + 2^{23} - 2^{18} - 2^{16} + 2^9\
&\phantom{2^31} + 2^{30} - 2^{28} + 2^{26} - 2^{24} + 2^{21} - 2^{16} - 2^{14} + 2^7\
&\phantom{2^{31} - 2^{30} + 2^{28} - 2^{26} }+2^{23} - 2^{21} + 2^{19} - 2^{17} + 2^{14} - 2^9 - 2^7 + 1\
 = & 2^{32} + ( - 2^{24}+2^{23}+ 2^{23}) + (2^{19} - 2^{18} - 2^{17} - 2^{16} - 2^{16})+ 1\
 = & 2^{32} + 1.
\end{align*}
More briefly, 
$$2^{2^5} + 1 = 4294967297 =  641 	imes 6700417$$
is composite.
\end{proof}

Exercise 1.3.43 ($F_5$ is composite.)

Answers

Comments

Exercise 1.3.43 ($F_5$ is composite.)

Answers

Comments

Add answer