5
$\begingroup$

This question already has an answer here:

Prove that $\gcd(2^{2^m}+1,2^{2^n}+1)=1$ if $m,n$ are positive integers.

Let $d=\gcd(2^{2^m}+1,2^{2^n}+1)$, then $d\mid 2^{2^m}+1$ and $d\mid2^{2^n}+1$ and then $d\mid2^{2^m}+1-2^{2^n}-1$, i.e. $d\mid2^{2^m}-2^{2^n}$ where we have taken $m>n$. Thus $d\mid2^{2^n}(2^{2^{m-n}}-1)$, but $d \nmid 2^{2^n}$ thus $d\mid2^{2^{m-n}}-1$.

Then how will I proceed??

$\endgroup$

marked as duplicate by Brian M. Scott, Johanna, user147263, Macavity, Joel Reyes Noche Feb 28 '15 at 4:02

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.

  • 1
    $\begingroup$ Note proper use of \gcd, \mid, and \nmid in my edits to the question. The expression $a|b$, coded by a|b, lacks proper spacing, but $a\mid b$, coded by a\mid b, looks different. Similarly \gcd not only prevents italicization, but also results in proper spacing in things like $a\gcd(b,c)$ (between $a$ and $\gcd$). ${}\qquad{}$ $\endgroup$ – Michael Hardy Feb 28 '15 at 1:12
  • 1
    $\begingroup$ Your arithmetic is a little off: $$\large2^{2^m}-2^{2^n} =2^{2^n}\left(2^{2^m-2^n}-1\right) =2^{2^n}\left(2^{2^n\left(2^{m-n}-1\right)}-1\right)\;.$$ $\endgroup$ – Brian M. Scott Feb 28 '15 at 1:13
  • 1
    $\begingroup$ See also proofwiki.org/wiki/Fermat_Numbers_are_Coprime $\endgroup$ – Fermat Feb 28 '15 at 1:14
  • 1
    $\begingroup$ Not to be a jerk about it, but $m \neq n$, right? $\endgroup$ – Robert Soupe Feb 28 '15 at 3:00
5
$\begingroup$

Let $a_n = 2^{2^n}+1$. Then:

$$ a_{n+m} = (a_n-1)^{2^m}+1, $$ hence: $$ a_{n+m}\equiv (-1)^{2^m}+1 = 2\pmod{a_n}, $$ from which it follows that: $$ \gcd(a_{n+m},a_{n}) = \gcd(2,a_n)=1 $$ since $a_n$ is odd.

$\endgroup$
  • 1
    $\begingroup$ I like this a little better than the method shown on wikipedia, which first requires using induction to prove that for $n\geq 2$, $$F_n = \prod_{k<m}F_k + 2$$ That makes their proof longer and less direct. $\endgroup$ – Mark Fischler Jan 10 '17 at 16:57
  • $\begingroup$ @MarkFischler: thank you, I appreciate that. Truth to be told, such identity is not that painful to prove, since $F_n-2$ is a telescopic product due to $a^2-1=(a-1)(a+1)$. $\endgroup$ – Jack D'Aurizio Jan 10 '17 at 17:43
0
$\begingroup$

${\bf Hint}\rm\quad\ \ \gcd(a\!+\!1,\,\ a^{\large 2K}\!+1)\ =\ gcd(a\!+\!1,\,\color{#0a0}2)\,$ by Euclid's gcd algorithm.

${\bf Proof}\rm\ \ \ mod\ a\!+\!1\!:\,\ \color{#c00}a^{\large 2K}\!+1\: \equiv\ (\color{#c00}{-1})^{\large 2K}\!+1\:\equiv\ \color{#0a0}2,\ \ {\rm by}\ \ \color{#c00}{a\equiv -1,}\, \ {\rm by}\, \ a\!+\!1\equiv 0$

Yours is case $\rm\,\ a=2^{\Large 2^{M}},\ \ 2K = 2^{\large N-M} \Rightarrow\ a^{\Large 2K}\! = 2^{\Large 2^{N}}, $ wlog $\rm\ N>M.$

Remark $\rm\ \gcd(a\!+\!1,f(a))\, =\, \gcd(a\!+\!1,f(-1))\,$ for any polynomial $\rm\,f(x)\,$ with integer coefficients, with proof exactly as above, except here we need to use the general Polynomial Congruence Rule vs. the Power or Product Rules.

$\endgroup$

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