# Prove $\gcd(a^{2^m}+1, a^{2^n}+1)$ is either $1$ or $2$ [duplicate]

Let a be a nonzero integer, $$m>n>0, m,n\in \mathbb{Z}$$.

(1)Prove that $$\gcd(a^{2^m}+1, a^{2^n}+1)$$ is either $$1$$ or $$2$$.

(2)Use this fact to prove that there are infinite number of primes.

My attempt on (1): the problem can be splitted into two cases.

If $$a$$ is an even number, then we only need to prove $$\gcd(a^{2^m}+1,a^{2^n}+1)$$ equals $$1$$ since odd numbers cannot have $$2$$ as divisor.

If $$a$$ is an odd number, then we only need to prove $$\gcd(a^{2^m}+1, a^{2^n}+1)$$ equals $$2$$ since $$a^{2^m}+1$$ and $$a^{2^n}+1$$ are both even.

Any hints would be appreciated!

## marked as duplicate by Robert Z, lulu, Vinyl_cape_jawa, 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(); } ); }); }); Feb 25 at 16:08

If $$m > n$$ then $$a^{2^n} +1$$ divides $$a^{2^m} - 1.$$ Because
$$(a^{2^n} + 1) \cdot (a^{2^n} -1) = (a^{2^{n+1}} - 1)$$ and So $$a^{2^n} +1 \mid a^{2^{n+1}} - 1$$ and since $$m > n$$ by similar reasoning we should also have $$a^{2^{n+1}} - 1 \mid a^{2^m} - 1.$$ So for $$m > n$$ we have $$a^{2^n} +1 \mid a^{2^m} - 1,$$ as claimed.
Also note that if $$c \mid a$$ then $$\text {gcd} (a+b,c) = \text {gcd}(b,c).$$
Therefore we have \begin{align} \text {gcd} (a^{2^m} + 1 , a^{2^n} + 1) & = \text {gcd} ((a^{2^m} - 1)+2 , a^{2^n} + 1). \\ & = \text {gcd} (2 , a^{2^n} + 1). \\ & = 1\ \text {or}\ 2. \end{align}