3
$\begingroup$

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$?

  • 2
    By "Fermat theorem", do you mean "Fermat number"?2011-09-30

5 Answers 5

14

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

  • 0
    @HenningMakholm Yes, It can be proved that $f_b$ divides $f_a-2$. But how it explains the desired proof.2015-03-21
10

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

4

${\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.