# Problems regarding GCD [duplicate]

If $$m > n$$ and $$a,m,n$$ are positive, with $$m$$ not equal to $$n$$, find the greatest common divisor of $$2^{2^m}+1, 2^{2^n}+1$$. Please solve this problem using Euclid's algorithm.

I tried to use Euclid's algorithm by first dividing $$2^{2^m}+1$$ by $$2^{2^n}+1$$, but I got stuck in the 2nd step while dividing $$2^{2^n}+1$$ by the difference of $$2^{2^m}+1$$ and $$2^{2^n}+1$$.

## marked as duplicate by Greg Martin, Cesareo, Adrian Keister, José Carlos Santos, Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 15 at 18:10

• math.stackexchange.com/questions/123524/… – lab bhattacharjee May 15 at 5:36
• There is no such thing as a "greatest common denominator". Two fractions will have a least common denominator. Two integers will have a greatest common divisor. Anyway, do you know what Euclid's Algorithm is? Do you know how to apply it? Where do you get stuck when you try to apply it to this question? We can't help you, if we don't know what you can do, and what you can't do. – Gerry Myerson May 15 at 6:13
• As written, the answer is $(a^2)^{n+1}$, obviously. PLease check the statement – Hagen von Eitzen May 15 at 6:13
• @Hagen, look at the edit history. A comedy of errors. – Gerry Myerson May 16 at 3:19
• @Garry Thanks for asking. I am now clear on this topic. I am now trying to further improve my understanding on Euclid's algorithm by solving more problems like this. – Rohan Kalluraya May 18 at 11:43

The first step in Euclid's algorithm:

If we let $$a_k = 2^{2^k}+1$$, and

$$g(m,n)=\sum _{j=1}^{2^{m-n}} (-1)^{j+1}2^{2^m-j 2^n}$$

then

$$a_m=a_ng(m,n)+2$$

The second step would be

$$a_n=2\left(\frac{a_n-1}{2}\right)+1$$

which shows that $$a_m,a_n$$ are coprime for $$m>n>0$$