2
$\begingroup$

This question already has an answer here:

The Fermat numbers are defined by $F_m = 2^{2^m} + 1$.

Prove that for $m \ne n$ we have $(F_m, F_n) = 1$.

I have to first prove that $F_{m+1} = F_0F_1 \cdots F_m + 2$ by representing $F_{m+1}$ in terms of $F_m$.

$\endgroup$

marked as duplicate by quid, Lord_Farin, André Nicolas, Jack D'Aurizio, saz Jan 24 '15 at 17:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ See also math.stackexchange.com/questions/123524, but since you wish another approach this isn't a duplicate. $\endgroup$ – punctured dusk Jan 24 '15 at 14:30
  • $\begingroup$ @barto I am new to this. Is there possibly a simpler way to prove this? $\endgroup$ – Victoria Azcarate Jan 24 '15 at 14:31
  • $\begingroup$ The duplicate I link to contains the desired proof version too. $\endgroup$ – quid Jan 24 '15 at 17:21
4
$\begingroup$

Your idea to prove $$ F_{m+1}=F_0 F_1\cdots F_m+2 $$ first is good. Note that $$ F_{m+1}=2^{2^{m+1}}+1=\left(\left(2^{2^{m}}\right)^2-1\right)+2=\left(2^{2^{m}}+1\right)\left(2^{2^{m}}-1\right)+2=$$ $$=F_m\left(2^{2^{m-1}}+1\right)\left(2^{2^{m-1}}-1\right)+2=F_m F_{m-1}\left(2^{2^{m-1}}-1\right)+2= $$ $$\cdots=F_mF_{m-1}\cdots F_1F_0+2.$$

Let now $F_m$ and $F_n$ be arbitarry distinct Fermat numbers. We may assume that $m>n$. Note that Fermat numbers are odd. Hence, if there were a prime number $p$ such that $p|F_m$ and $p|F_n$, then $p$ is an odd prime number. We have proved that $$ F_m=F_{m-1}\cdots F_n\cdots F_1F_0+2 \tag1$$ (since $n<m$ the number $F_n$ appears in the product $F_{m-1}\cdots F_1 F_0$). Now we have a contradiction: if $p|F_m$ and $p|F_n$, then (1) gives $p|2$. But this is impossible as $p$ is an odd prime number.

$\endgroup$
  • $\begingroup$ Okay, I understand that much. Now what do I do next? $\endgroup$ – Victoria Azcarate Jan 24 '15 at 14:44
  • $\begingroup$ @VictoriaAzcarate I have continued with the answer. I hope that now you can see how we get the product of Fermat numbers. $\endgroup$ – Janko Bracic Jan 24 '15 at 14:50
  • $\begingroup$ Okay, now how do I prove what I am supposed to prove? $\endgroup$ – Victoria Azcarate Jan 24 '15 at 14:53
  • $\begingroup$ So after you wrote "But this is impossible as p is an odd prime number", we can say that the $(F_m,F_n)=1$, Right? $\endgroup$ – Victoria Azcarate Jan 24 '15 at 15:11
  • $\begingroup$ @VictoriaAzcarate Yes, that is the conclusion. $\endgroup$ – Janko Bracic Jan 24 '15 at 15:12
5
$\begingroup$

Hint $\ $ A simpler and more general way to proceed is to note that it is a special case of the Euclidean algorithm reduction below, for $\rm\ c=2^{\Large 2^{N}},\ \ 2k = 2^{\large \,M-N}\,\Rightarrow\ c^{\Large 2k} =\, 2^{\Large 2^{M}}$

$\phantom{\bf Hint}\rm\qquad\qquad \gcd(a,\,b)\quad \ =\ \quad gcd(a,\ \color{#c00}{b\ mod\ a})\qquad $ (Euclidean reduction)

$\phantom{\bf Hint}\!\!\!\rm\Rightarrow\ \ \gcd(c+1,\,\ c^{\large 2\,k}\!+1)\ =\ gcd(c+1,\:\color{#c00}2)$

${\bf Proof}\rm\ \ \ mod\ c+1\!:\,\ c^{\large 2\,k}\!+1\: \equiv\ (-1)^{\large 2\,k}\!+1\:\equiv\ \color{#c00}2,\ \ {\rm by}\ \ c\equiv -1\quad {\bf QED}$

This easily generalizes from $\rm\,f(c) = c^{2k}-1\,$ to any polynomial $\rm f(x)$ with integer coef's

$\rm\qquad\qquad gcd(c\!-\!n,f(c))\, =\, gcd(c\!-\!n,f(n))\ \ $ by $\rm\ \ {\rm mod}\ c\!-\!n\!:\,\ c\equiv n\,\Rightarrow\, f(c)\equiv f(n)$

by the Polynomial Congruence Rule. Notice how much clearer the deduction is when viewed this way - it amounts simply to a polynomial evaluation.

This is a prototypical example of the power of congruence arithmetic - it allows us to replace complex manipulation of divisibility relations by simpler congruence operations - which are far more intuitive given our well-honed intuition on analogous integer arithmetic.

Remark $ $ Alternatively, if congruence arithmetic is not familiar, one could instad note 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 more ingenuity vs. mechanical application of the Euclidean reduction $\rm\ \gcd(a,b)\, =\, \gcd(a,\:b\ mod\ a). $

$\endgroup$
  • $\begingroup$ Truthfully, I don't understand most of that notation. I haven't covered most of it. Can you perhaps give me a simpler proof, possibly on the path that Janko has taken? $\endgroup$ – Victoria Azcarate Jan 24 '15 at 14:45
  • $\begingroup$ @Victoria Which notation is problematic? $\endgroup$ – Bill Dubuque Jan 24 '15 at 14:50
  • $\begingroup$ The mod is probelmatic $\endgroup$ – Victoria Azcarate Jan 24 '15 at 14:54
  • $\begingroup$ @Victoria $\ b\ {\rm mod}\ a\, $ is the remainder left on dividing $\,b\,$ by $\,a,\,$ as used in the reduction step in the Euclidean algorithm for the gcd. So the proof is essentially a special case of Euclid's algorithm (this way you don't need to employ any special properties of Fermat Numbers). $\endgroup$ – Bill Dubuque Jan 24 '15 at 14:58
  • $\begingroup$ @VictoriaAzcarate If you haven't yet met congruence (modular) arithmetic then you can employ the equivalent divisibity form in the Remark, i.e. $\rm\ c\!+\!1 \mid c^{2k}\!-\!1 = (c^{2k}\!+\!1)-2.\ $ $\endgroup$ – Bill Dubuque Jan 24 '15 at 15:21
1
$\begingroup$

To see that $F_{m+1} = F_0 F_1\cdots F_m + 2$, proceed as follows.

\begin{align}F_{m+1} &= (2^{2^m} - 1) + 2\\ &= [(2^{2^{m-1}})^2 - 1] + 2\\ &= (2^{2^{m-1}} - 1)F_m + 2\\ &= [(2^{2^{m-2}})^2 - 1]F_m + 2\\ &= (2^{2^{m-2}} - 1)F_{m-1}F_m + 2\\ &\ldots\\ &= (2^{2^0} - 1)F_1F_2\cdots F_m + 2\\ &= F_0F_1\cdots F_m + 2. \end{align}

Now to prove the theorem, let $d = \gcd(F_m,F_n)$, and assume, without loss of generality, that $m > n$. Then $d|F_m$ and $d|F_n$, which implies $d|F_0\cdots F_{m-1}$, since $F_n$ is a factor of $F_0\cdots F_{m-1}$ when $n < m$. Therefore, $d|(F_m - F_0\cdots F_{m-1})$, or $d|2$. Since $d$ is an odd positive number, the condition $d|2$ implies $d = 1$.

$\endgroup$

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