How to find $\gcd(a^{2^m}+1,a^{2^n}+1)$ when $m \neq n$? [duplicate]

How to prove the following equality?

For $m\neq n$,

$\gcd(a^{2^m}+1,a^{2^n}+1) = 1 $ if $a$ is an even number

$\gcd(a^{2^m}+1,a^{2^n}+1) = 2 $ if $a$ is an odd number

Thanks in advance.

Solution 1:

Let $p$ divides $a^{2^n}+1\implies a^{2^n}\equiv-1\pmod p$

If $m>n,$ taking $2^{m-n}$th power, $(a^{2^n})^{2^{m-n}}\equiv(-1)^{2^{m-n}}\pmod p\implies a^{2^m}\equiv1\pmod p$

So, $p$ divides $ a^{2^m}-1$

If $p$ divides $ a^{2^m}+1,p$ will divide $(a^{2^m}+1)-(a^{2^m}-1)=2$

So, if $a$ is even, $a^{2^n}+1$ will be odd $\implies p=1\implies $ gcd$(a^{2^m}+1,a^{2^n}+1)=1$

Similarly, for odd $a$

Alternatively, WLOG let $m>n,a^{2^n}=b$(say) and $m=n+r$ where integer $r>0$

$\implies a^{2^m}+1=a^{2^{n+r}}+1=(a^{2^n})^{2^r}+1=b^{2^r}+1$

Now, $b^2-1=(b+1)(b-1)$

$(b^2)^2-1=(b^2+1)(b^2-1)=(b^2-1)(b+1)(b-1)$

$\cdots$

$b^{2^r}-1=(b^{2^{r-1}}+1)(b^{2^{r-1}}-1)\cdots(b^4+1)(b^2+1)(b+1)$

Now, $gcd(b^{2^r}+1,b^{2^r}-1)=gcd(b^{2^r}+1-(b^{2^r}-1),b^{2^r}-1)$

$=gcd(2,b^{2^r}-1)= \begin{cases} 2 &\mbox{if } b \mbox{ is odd} \\ 1 & \mbox{if } b \mbox{ is even }\end{cases} $

As $(b+1)$ divides $(b^{2^r}-1),gcd(b^{2^r}+1, b+1)$ will divide $gcd(b^{2^r}+1,b^{2^r}-1)$

Observe that if $b$ is odd, $gcd(b^{2^r}+1,b^{2^r}-1)=2$ and $b^{2^r}+1, b+1$ are both even , hence $ gcd(b^{2^r}+1, b+1)=2\implies gcd(a^{2^m}+1,a^{2^n}+1)=2$

Similarly, for even $b$

Solution 2:

Hint $\rm\,\ d\mid 1\!+\!a^{\large 2^N}\!\!\!,\,1\!+\!a^{\large 2^{N+K}}\!\!\Rightarrow\: mod\ d\!:\ a^{\large 2^N}\!\equiv \color{#c00}{-1}\equiv a^{\large 2^{N+K}}\!\! \equiv(a^{\large2^N}\!)^{\large {2^K}}\!\!\!\equiv(\color{#c00}{-1})^{\large {2^K}}\!\!\equiv\color{#c00}1\:\Rightarrow\:d\mid\color{#c00}{1\!+\!1}$

Solution 3:

Wlog. $m>n$. Let $p$ be a divisor of $\gcd(a^{2^m}+1,a^{2^n}+1)$,. Then especially $p|a^{2^m}+1$, i.e. $a^{2^n}\equiv -1\pmod p$ and $$a^{2^m}=(a^{2^n})^{2^{m-n}}\equiv (-1)^{2^{m-n}}\equiv 1^{2^{m-n-1}}\equiv 1\pmod p.$$ As also $p|a^{2^m}+1$, we conclude $p|2$, i.e. $$ \gcd(a^{2^m}+1,a^{2^n}+1)=2^k\qquad\text{for some }k\ge0.$$ If $a$ is even, $a^{2^n}+1$ and $a^{2^m}+1$ are odd, thus implying $k=0$. If $a$ is odd, then $a^{2^n}+1$ and $a^{2^m}+1$ are even, hence $k\ge1$. On the othre hand, odd squares are always $\equiv 1\pmod 8$, hence we take gcd of numbers $\equiv 2\pmod 8$, i.e. they are not multiples of $4$, hence $k=1$.