0
$\begingroup$

We are discussing Fermat numbers in class, and one of the claims brought up is as follows:

"For any integer $n \ge 1$, the $n$th Fermat number is $F(n)$ = $2 + \prod_{i=0}^{n-1}F(i)$."

I have not been able to find any proofs online, but I would really like to know how a Fermat number can be represented in this form (as 2 plus the product of past Fermat numbers). Are Fermat numbers not prime, or have I confused myself? It doesn't seem intuitive to me, but I could be wrong.

$\endgroup$
1
  • 2
    $\begingroup$ Hint: what's $(x-1)(x+1)$? How about $(x-1)(x+1)(x^2+1)$? It's also not true that Fermat numbers are prime. The small ones up to $F(4)$ are prime, but after that not a single more Fermat prime has been found (and very few are expected). Finally, what do you find about this equation that contradicts the possibility that they are prime? $\endgroup$
    – Erick Wong
    Jan 30, 2013 at 4:17

2 Answers 2

2
$\begingroup$

$$(x^{2^n}-1)=(x^{2^{n-1}}+1)(x^{2^{n-1}}-1)=(x^{2^{n-1}}+1)(x^{2^{n-2}}+1)(x^{2^{n-3}}-1)$$ $$=(x^{2^{n-1}}+1)(x^{2^{n-2}}+1)(x^{2^{n-3}}+1)(x^{2^{n-4}}+1)...(x^4+1)(x^2+1)(x+1)(x-1)$$ $$\frac{x^{2^n}-1}{x-1}=\prod_{k=0}^{n-1}(x^{2^k}+1)$$ $$2^{2^n}-1=\prod_{k=0}^{n-1}(2^{2^k}+1)$$ $$2^{2^n}+1=2+\prod_{k=0}^{n-1}(2^{2^k}+1)$$ $$F_n=2+\prod_{k=0}^{n-1}F_k$$

$\endgroup$
1
$\begingroup$

Let $f_n = 2^{2^n}+1$.
There is an obvious recurrence relation: $f_{n+1} = (f_n-1)^2 + 1$.
Now, \begin{align} f_{n+1} &= f_n^2 - 2f_n + 2\\ &= f_n(f_n-2)+2\\ &= f_n(f_{n-1}(f_{n-1} - 2)) + 2\\ &= f_nf_{n-1}(f_{n-2}(f_{n-2}-2)) + 2\\ &\cdots\\ &= f_nf_{n-1}...f_1f_0 + 2\\ &= 2 + \prod_0^n f_k. \end{align}

Because $f_0$ is odd and greater than $1$, any prime dividing $f_n$ cannot divide $f_{n+1}$, meaning that the Fermat numbers are all relatively prime, although not necessarily primes themselves.

$\endgroup$

You must log in to answer this question.