On the GCD of a Pair of Fermat Numbers

Solution 1:

Hint: Show that $f_b$ divides $f_a-2$.

Solution 2:

Claim. $f_n=f_0\cdots f_{n-1}+2$.

The result holds for $f_1$: $f_0=2^{2^0}+1 = 2^1+1 = 3$, $f_1=2^{2}+1 = 5 = 3+2$.

Assume the result holds for $f_n$. Then $$\begin{align*} f_{n+1} &= 2^{2^{n+1}}+1\\ &= (2^{2^n})^2 + 1\\ &= (f_n-1)^2 +1\\ &= f_n^2 - 2f_n +2\\ &= f_n(f_0\cdots f_{n-1} + 2) -2f_n + 2\\ &= f_0\cdots f_{n-1}f_n + 2f_n - 2f_n + 2\\ &= f_0\cdots f_n + 2, \end{align*}$$ which proves the formula by induction. $\Box$

Now, let $d$ be a common factor of $f_b$ and $f_a$. Then $d$ divides $f_0\cdots f_{a-1}$ (because it's a multiple of $f_b$) and divides $f_a$. That means that it divides $$f_a - f_0\cdots f_{a-1} = (f_0\cdots f_{a-1}+2) - f_0\cdots f_{a-1} = 2;$$ but $f_a$ and $f_b$ are odd, so $d$ is an odd divisor of $2$. Therefore, $d=\pm 1$. So $\gcd(f_a,f_b)=1$.

Solution 3:

${\bf Hint}\rm\quad\ \ \gcd(c+1,\,\ c^{\large 2\,k}\!+1)\ =\ gcd(c+1,\:2)$

${\bf Proof}\rm\ \ \ mod\ c+1\!:\,\ c^{\large 2\,k}\!+1\: \equiv\ (-1)^{\large 2\,k}\!+1\:\equiv\ 2,\ \ {\rm by}\ \ c\equiv -1\quad {\bf QED}$

Specializing $\rm\,\ c=2^{\Large 2^{B}},\ \ 2\,k = 2^{\large \,A-B}\ \Rightarrow\ c^{\Large\, 2\,k} = 2^{\Large 2^{A}}\ $ immediately yields your claim.

Remark $\ $ Aternatively, one could employ 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 some ingenuity, whereas the above proof does not, being just a trivial congruence calculation using the modular reduction property of the $\rm\:gcd,\:$ namely $\rm\ \gcd(a,b)\, =\, \gcd(a,\:b\ mod\ a),\:$ a reduction which applies much more generally. $ $ Said equivalently, the result follows immediately by applying a single step of the Euclidean algorithm. Notice how abstracting the problem a little served to greatly elucidate the innate structure.

Solution 4:

I'm going to be cheeky and flesh out Henning Malkholm's answer, since it's been seven years since this was posted (so if it was indeed homework, it was probably due in by now) and his implicit solution is the best I've seen to this problem. If this bothers you, Henning, let me know and I'll take this down. (I don't have enough reputation to comment directly because I'm new here)

Suppose $b = a + k$ for $k$ a positive integer. Then by basic algebra $$ F_b - 2 = 2^{2^b} - 1 = \left( 2^{2^{a}} \right)^{2^{k}} - 1$$ so, expanding using the geometric sum, $$ F_b - 2 = \left( 2^{2^a} + 1 \right) \left\{ \left(2^{2^a}\right)^{2^k-1} - \left(2^{2^a}\right)^{2^k-2} + \cdots -1\right\} $$ So substituting the defining formula gives $$ F_b - 2 = F_a \cdot \left( 2^{2^b-2^a} - \cdots - 1 \right) $$ In particular, $F_b-2$ is a multiple of $F_a$. However, successive odd numbers are relatively prime so no factor of $F_a$ can be a factor of $F_b$