Difference between revisions of "Fermat number"

Latest revision as of 17:18, 25 August 2009

A Fermat number is a number of the form $2^{2^n} + 1$ where $n$ is a nonnegative integer.

The first five Fermat numbers (for $n=0,1,2,3,4$ ) are $\begin{align*} F_0 &= 2^{2^0}+1 = 3\\ F_1 &= 2^{2^1}+1 = 5\\ F_2 &= 2^{2^2}+1 = 17\\ F_3 &= 2^{2^3}+1 = 257\\ F_4 &= 2^{2^4}+1 = 65537. \end{align*}$ A prime Fermat number is known as a Fermat prime. Each of the first five Fermat numbers is a Fermat prime. Based on these results, one might conjecture (as did Fermat) that all Fermat numbers are prime. However, this fails for $n=5$ : $F_5 = 2^{2^5}+1 = 4294967297 = 641 \cdot 6700417$ . In fact, the primes listed above are the only Fermat numbers known to be prime. The Fermat number $F_n$ is known to be composite for $5 \leq n \leq 32$ .

Relative primality of Fermat numbers

The Fermat numbers $F_m$ and $F_n$ are relatively prime for all $m \neq n$

Proof

We prove that the Fermat numbers satisfy the following recursion, from which the claimed result will follow: for all $n \geq 0$ , $F_{n + 1} = F_0 \cdot F_1 \cdot F_2 \cdots F_n + 2.$

We proceed by induction. For $n = 0$ we have $F_1 = 5 = 3 + 2 = F_0 + 2$ , as desired. Suppose that $F_k = F_0 \cdots F_{k - 1} + 2$ . Now observe that $\begin{align*} F_{k + 1} & = 2^{2^{k + 1}} + 1 \\ & = \left(\left(2^{2^{k}}\right)^2 + 2 \cdot 2^{2^k} + 1\right) - 2\cdot 2^{2^k} \\ & = (F_k)^2 - 2F_k + 2 \\ & = (F_0 \cdot F_1\cdots F_{k - 1} + 2)\cdot F_k - 2F_k + 2 \\ & = F_0 \cdot F_1 \cdots F_{k - 1} \cdot F_k + 2, \end{align*}$ as desired.