# How to show that: $\gcd \Big(2^{2^a}+1 , 2^{2^b}+1\Big)=1$

How to show that: $$\gcd \Big(2^{2^a}+1 , 2^{2^b}+1 \Big)=1$$

-
Is there any condition over $a$ and $b$. What are $a$ and $b$? Sorry for asking. –  Babak S. Nov 30 '12 at 15:19
@BabakSorouh No.n is integer. –  World Nov 30 '12 at 15:26
If $a=b$, the claim is false. In general, $\gcd(2^n+1,2^m+1)=2^{\gcd(n,m)}+1$. –  Hagen von Eitzen Nov 30 '12 at 15:26
Ooops, ignore the second half of my previous comment –  Hagen von Eitzen Nov 30 '12 at 15:32
@HagenvonEitzen thanks, hypothesis is $a \neq b$ –  World Nov 30 '12 at 15:41

We know $(x-y)\mid(x^c-y^c)$ where $x,y,c$ are natural numbers.

Putting $x=a^{2^n},b=-1, c=2^{m-n}$

$$\{a^{2^n}-(-1)\}\mid \{(a^{2^n})^{2^{m-n}}-(-1)^{2^{m-n}}\}$$ if $m>n$ where $a,m,n$ are natural numbers.

$$\implies (a^{2^n}+1)\mid (a^{2^m}-1)$$ if $m>n$

Now, $$(a^{2^m}-1,a^{2^m}+1)=(a^{2^m}-1,a^{2^m}+1-(a^{2^m}-1))=(a^{2^m}-1,2)$$ is $2$ if $a$ is odd, is $1$ if $a$ is even

So, $$(a^{2^n}+1,a^{2^m}+1)$$ will be $1$ or $2$ accordingly.

-
explain more about : $\{a^{2^n}-(-1)\}\mid \{(a^{2^n})^{2^{m-n}}-(-1)^{2^{m-n}}\}$ , i don't know this expression. –  World Nov 30 '12 at 17:13
@World, please let me know if the edited answer can not clarify your query. –  lab bhattacharjee Nov 30 '12 at 17:31
$\Big((a^{2^m}-1,2)$ So,$(a^{2^n}+1,a^{2^m}+1)Big)$} isn't clear. –  World Nov 30 '12 at 18:07
@World, observe that $(a^{2^n}+1,a^{2^m}+1)\mid (a^{2^m}-1,a^{2^m}+1)$ –  lab bhattacharjee Nov 30 '12 at 18:13

Assume WLOG that $b>a$.

Note that $(2^{2^a}+1)|((2^{2^a})^{2^{b-a}}-1)=(2^{2^b}-1)$. (This follows from the fact that $x^2-1|x^{2^k}-1$ and $x+1|x^2-1$ for integer x and any positive integer k)

Thus, it follows that $2^{2^b}-1=k(2^{2^a}+1)$. Now add two to both sides to get:

$$2^{2^b}+1=k(2^{2^a}+1)+2$$ Thus, $\gcd(2^{2^a}+1,2^{2^b}+1)|2$. Since both numbers are odd it follows that $\gcd(2^{2^a}+1,2^{2^b}+1)=1$

-

Hint:

Call $2^{2^n}+1=F_n$, and then show that $F_n = F_{n-1}...F_1 + 2$.

Now any number greater than $2$ that divides $F_m$ for $n>m$ will divide only part of the right side, and therefore not the left.

-
can you explain more ? –  World Nov 30 '12 at 15:37
Don't you mean $F_n=2F_{n-1}...F_1$? –  Thomas Andrews Nov 30 '12 at 15:46
@World: I had a severe typo previously - $F_n$ should be $2^{2^n} + 1$ instead of $2^{2^n}$. But I'll write a bit now that I'm not on a machine with poor typing attributes. –  mixedmath Nov 30 '12 at 16:16