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$.
 A: Hint $\ $ A simpler and more general way to proceed is to note that it is a  special case of the Euclidean algorithm reduction below, for $\rm\ c=2^{\Large 2^{N}},\ \ 2k = 2^{\large \,M-N}\,\Rightarrow\ c^{\Large 2k} =\, 2^{\Large 2^{M}}$
$\phantom{\bf Hint}\rm\qquad\qquad \gcd(a,\,b)\quad \ =\ \quad gcd(a,\ \color{#c00}{b\ mod\ a})\qquad $ (Euclidean reduction)
$\phantom{\bf Hint}\!\!\!\rm\Rightarrow\ \  \gcd(c+1,\,\ c^{\large 2\,k}\!+1)\ =\ gcd(c+1,\:\color{#c00}2)$ 
${\bf Proof}\rm\ \ \ mod\ c+1\!:\,\  c^{\large 2\,k}\!+1\: \equiv\ (-1)^{\large 2\,k}\!+1\:\equiv\ \color{#c00}2,\ \ {\rm by}\ \ c\equiv -1\quad {\bf QED}$  
This easily generalizes from $\rm\,f(c) = c^{2k}-1\,$ to any polynomial $\rm f(x)$ with integer coef's
$\rm\qquad\qquad  gcd(c\!-\!n,f(c))\, =\, gcd(c\!-\!n,f(n))\ \ $ by $\rm\ \ {\rm mod}\ c\!-\!n\!:\,\ c\equiv n\,\Rightarrow\, f(c)\equiv f(n)$
by the Polynomial Congruence Rule. Notice how much clearer the deduction is when viewed this way - it amounts simply to a polynomial evaluation. 
This is a prototypical example of the power of congruence arithmetic - it allows us to replace complex manipulation of divisibility relations by simpler congruence operations - which are far more intuitive given our well-honed intuition on analogous integer arithmetic.
Remark $ $ Alternatively, if congruence arithmetic is not familiar, one could instad note that  $\rm\:c^{\large 2\,k}\!+1\, =\, (c^{\large 2\,k}-1) + 2\:\equiv\: 2\pmod{c+1},\, $ by $\rm\ c+1\ |\ c^{\large 2}-1\ |\ c^{\large 2\,k}\!-1,\, $ but this requires more ingenuity vs. mechanical application of the Euclidean reduction $\rm\ \gcd(a,b)\, =\, \gcd(a,\:b\ mod\ a). $ 
A: Your idea to prove
$$ F_{m+1}=F_0 F_1\cdots F_m+2 $$
first is good. Note that
$$ F_{m+1}=2^{2^{m+1}}+1=\left(\left(2^{2^{m}}\right)^2-1\right)+2=\left(2^{2^{m}}+1\right)\left(2^{2^{m}}-1\right)+2=$$
$$=F_m\left(2^{2^{m-1}}+1\right)\left(2^{2^{m-1}}-1\right)+2=F_m F_{m-1}\left(2^{2^{m-1}}-1\right)+2= $$
$$\cdots=F_mF_{m-1}\cdots F_1F_0+2.$$
Let now $F_m$ and $F_n$ be arbitarry distinct Fermat numbers. We may assume that $m>n$.
Note that Fermat numbers are odd. Hence, if there were a prime number $p$ such that $p|F_m$
and $p|F_n$, then $p$ is an odd prime number. We have proved that
$$ F_m=F_{m-1}\cdots F_n\cdots F_1F_0+2 \tag1$$
(since $n<m$ the number $F_n$ appears in the product $F_{m-1}\cdots F_1 F_0$). Now we have
a contradiction: if $p|F_m$ and $p|F_n$, then (1) gives $p|2$. But this is impossible as $p$ is an odd prime number.
A: 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$.
