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

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

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

• 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{}$ – Michael Hardy Feb 28 '15 at 1:12
• 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)\;.$$ – Brian M. Scott Feb 28 '15 at 1:13
• – Fermat Feb 28 '15 at 1:14
• Not to be a jerk about it, but $m \neq n$, right? – Robert Soupe Feb 28 '15 at 3:00

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.

• 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. – Mark Fischler Jan 10 '17 at 16:57
• @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)$. – Jack D'Aurizio Jan 10 '17 at 17:43

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