<s>[INST] Prove that distinct Fermat Numbers are relatively prime The Fermat numbers are defined by $F_m = 2^{2^m} + 1$.
Prove that for $m \ne n$ we have $(F_m, F_n) = 1$.
I have to first prove that $F_{m+1} = F_0F_1 \cdots F_m + 2$ by representing $F_{m+1}$ in terms of $F_m$.
 [/INST] To see that $F_{m+1} = F_0 F_1\cdots F_m + 2$, proceed as follows.
\begin{align}F_{m+1} &= (2^{2^m} - 1) + 2\\
&= [(2^{2^{m-1}})^2 - 1] + 2\\
&= (2^{2^{m-1}} - 1)F_m + 2\\
&= [(2^{2^{m-2}})^2 - 1]F_m + 2\\
&= (2^{2^{m-2}} - 1)F_{m-1}F_m + 2\\
&\ldots\\
&= (2^{2^0} - 1)F_1F_2\cdots F_m + 2\\
&= F_0F_1\cdots F_m + 2.
\end{align}
Now to prove the theorem, let $d = \gcd(F_m,F_n)$, and assume, without loss of generality, that $m > n$. Then $d|F_m$ and $d|F_n$, which implies $d|F_0\cdots F_{m-1}$, since $F_n$ is a factor of $F_0\cdots F_{m-1}$ when $n < m$. Therefore, $d|(F_m - F_0\cdots F_{m-1})$, or $d|2$. Since $d$ is an odd positive number, the condition $d|2$ implies $d = 1$.
</s>