Fermat numbers and GCD

Question

I've been working with the Fermat numbers recently but this problem has really tripped me up. If the Fermat theorem is set as $f_a=2^{2^a}+1$, then how can we say that for an integer $b$ less than $a$ that $\gcd(f_b,f_a)=1$?

Answer 1

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

Answer 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$.

Answer 3

HINT $\rm\ \ \gcd(c+1,\ c^{2\:k}+1)\ =\ gcd(c+1,\:2)$

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

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

REMARK $\ $ Aternatively, one could employ that $\rm\:c^{2\:k}+1\: =\: (c^{2\:k}-1) + 2\:\equiv\: 2\pmod{c+1}\ $
by $\rm\ c+1\ |\ c^2-1\ |\ c^{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.