# On the GCD of a Pair of Fermat Numbers

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

• By "Fermat theorem", do you mean "Fermat number"? – Arturo Magidin Sep 30 '11 at 2:33

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

• Simpler than mine! I'm tempted to delete mine and just leave yours... – Arturo Magidin Sep 30 '11 at 2:47
• It's more "less detailed" than "simpler", I think. The question looked like it might be homework. – Henning Makholm Sep 30 '11 at 2:59
• Perhaps: 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. – Arturo Magidin Sep 30 '11 at 3:05
• Assuming that $b<a$, of course... – Thomas Andrews Jan 23 '15 at 14:38
• @ThomasAndrews: Yes, but that's stipulated in the question. – Henning Makholm Jan 23 '15 at 14:40

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.

• More generally see here for $\large \,\gcd(a^m+1,a^n+1)\ \$ – Bill Dubuque Jun 5 at 2:50

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

This is because the Fermat numbers belong to the companion Lucas sequence $$V(3,2) = 2^{k} + 1$$. Hence, all the prime factors of either $$V_{p}$$ where $$p \neq 3$$ is a prime, or $$V_{2^{n}}$$, are primitive; that is, they enter the sequence for the first time as factors at that very term.

So, as every prime factor of $$f_{a}$$ is primitive, it follows that $$gcd(f_{a},f_{b}) = 1$$ when $$b < a$$.