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.

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

share|improve this question
1  
Is there any condition over $a$ and $b$. What are $a$ and $b$? Sorry for asking. –  B. S. Nov 30 '12 at 15:19
    
@BabakSorouh No.n is integer. –  World Nov 30 '12 at 15:26
2  
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

3 Answers 3

up vote 1 down vote accepted

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.

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

share|improve this answer

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.

share|improve this answer
    
can you explain more ? –  World Nov 30 '12 at 15:37
1  
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

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.