# $(a^{2^n}+1,a^{2^m}+1)=1 or 2$ [duplicate]

Prove that if $m\not =n,a$ are positive integers then $(a^{2^n}+1,a^{2^m}+1)$ is $1$ if $a$ is even and $2$ if $a$ is odd.

I solve the problem in the following way: I assume that $m>n$ then $$a^{2^m}+1=a^{2^m}-1+2$$ With this expression if I take a divisor prime $p$ of $a^{2^n}+1$ then if $p|a^{2^m}+1$ this prime must divide 2 and the result follows.

But, how can I prove this statement without use of primes? This exercise appears before the concept of prime is introduced then I prefer do not use it.

Any idea?

Thanks!

## marked as duplicate by lab bhattacharjee 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(); } ); }); }); Aug 27 '15 at 16:27

• There's an $m \neq n$ constraint missing. – Daniel Fischer Aug 27 '15 at 14:09
• If $m≠n$ then it is true. Do you have any idea about Fermat numbers? – tatan Aug 27 '15 at 14:11

If we have $n < m$, then

$$(a^{2^n} + 1)\cdot (a^{2^n} - 1) = a^{2^{n+1}} - 1$$

shows $(a^{2^n}+1) \mid (a^{2^{n+1}}-1)$. Then

$$(a^{2^k}-1)\cdot(a^{2^k}+1) = a^{2^{k+1}}-1$$

shows $(a^{2^{n+1}}-1) \mid (a^{2^m}-1)$, and thus

$$\gcd(a^{2^m}+1, a^{2^n}+1) = \gcd((a^{2^m}-1)+2,a^{2^n}+1) = \gcd(2, a^{2^n}+1).$$

• Jmmm... If $a|c$ then $gcd(a+b,c)=gcd(b,c)$? Thanks! – YTS Aug 27 '15 at 14:23
• If $c\mid a$, not if $a\mid c$. If we write $a = k\cdot c$, it becomes $\gcd(a+b,c) = \gcd(a+b-kc,c) = \gcd(b,c)$. – Daniel Fischer Aug 27 '15 at 14:24