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$?
Fermat numbers and GCD
-
2By "Fermat theorem", do you mean "Fermat number"? – 2011-09-30
4 Answers
Hint: Show that $f_b$ divides $f_a-2$.
-
0Simpler than mine! I'm tempted to delete mine and just leave yours... – 2011-09-30
-
0It's more "less detailed" than "simpler", I think. The question looked like it might be homework. – 2011-09-30
-
0Perhaps: but you don't need to establish the precise formula like I did, but rather just use a "difference of $2^b$th powers" factorization, which is simpler. – 2011-09-30
-
0Assuming that $b – 2015-01-23
-
0@ThomasAndrews: Yes, but that's stipulated in the question. – 2015-01-23
-
0Ah, I scanned for $b – 2015-01-23
-
0@HenningMakholm Yes, It can be proved that $f_b$ divides $f_a-2$. But how it explains the desired proof. – 2015-03-21
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$.
${\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.
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$