I'm working on some proofs on a recurrence relation with Fermat numbers.

a). Prove with Fermat numbers $f_n = 2^{2^n} + 1$ that:

$$ f_0 \cdot f_1 \cdot f_2 \cdot f_3 \cdots f_{n-1} = f_n - 2$$

b). Prove that $f_n$ is relatively prime with $f_0, f_1, f_2, ... , f_{n-1}$. In other words:

for any $n$, $f_n$ is not divisible with any factors of its previous Fermat number.

In my attempt on (a) I used the sum of the powers of $2$ :

$$2^0 + 2^1 + 2^2 + 2^3 + ... + 2^n = 2^{n+1} - 1$$

but I didn't come very far.

Some help would be very much appreciated.

  • $\begingroup$ For (a), concentrate on $e_n:=2^{2^n} = f_n-1.$ What do you know about $e_n$ and $e_{n-1}?$ The $f_n$ is OEIS sequence A000215 and $e_n$ is OEIS sequence A001146.. $\endgroup$ – Somos Nov 14 '17 at 18:38

a) If $f_0\times f_1\times\cdots\times f_{n-1}=f_n-2$, then\begin{align}f_0\times f_1\times\cdots\times f_{n-1}\times f_n&={f_n}^2-2f_n\\&=\left(2^{2^n}+1\right)^2-2\times\left(2^{2^n}+1\right)\\&=2^{2\times2^n}+2\times2^{2^n}+1-2\times2^{2^n}-2\\&=2^{2^{n+1}}+1-2\\&=f_{n+1}-2.\end{align}

b) If $p$ is a prime number which divides $f_n$ and $f_m$, with $n<m$, then, $p$ divides both $f_0\times f_1\times\cdots\times f_m$ and $f_m$. Therefore, $p$ divides their difference, which is $2$. Since $p$ is prime, $p=2$, but this is impossible, because the Fermat primes are odd. This proves that distinct Fermat numbers are relatively prime.

For each $n\in\mathbb N$, let $p_n$ be the smallest prime factor of $f_n$. Then $(p_n)_{n\in\mathbb N}$ is an injective sequence of prime numbers. Therefore, there are infinitely many prime numbers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.