Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
By "Fermat theorem", do you mean "Fermat number"? –  Arturo Magidin Sep 30 '11 at 2:33

3 Answers 3

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

share|improve this answer
    
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

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.