Exercise 1.2.49* (Value of $(a^{2^m} + 1, a^{2^n} + 1)$)

Proof. We write $m\wedge n$ the g.c.d. of $m$ and $n$.

(a)

Let $a$ be an integer. Assume that $m>n$. We start from $$a^{2^n}\equiv -1(\mathit{mod}{a}^{2^n}+1).$$

By hypothesis, $m-n>0$, so $2^{m-n}$ is even. Therefore

$$a^{2^m}={\left(a^{2^n}\right)}^{2^{m-n}}\equiv {(-1)}^{2^{m-n}}\equiv 1(\mathit{mod}{a}^{2^n}+1).$$

This proves $a^{2^n}+1\mid a^{2^m}-1.$

(b)

We must compute $d=(a^{2^m}+1)\wedge (a^{2^n}+1)$, where $m\ne n$. The symmetry of the problem allows us to assume that $m>n$.

By definition of the g.c.d., $d\ge 0$ and $d\mid a^{2^n}+1,d\mid a^{2^m}+1$.

By part (a), knowing that $m>n$, $d\mid a^{2^m}-1$. Therefore $d\mid (a^{2^m}+1)-(a^{2^m}-1)$, so $d\mid 2$, where $d\ge 0$. Thus $d=1$ or $d=2$.

If $a$ is even, $a^{2^m}+1$ is odd, i.e. $2\nmid a^{2^m}+1$. Therefore $d=1$.

If $a$ is odd, $a^{2^m}+1$ and $a^{2^n}+1$ are both even. Therefore $2\mid d$, so $d=2$.

$$a^{2^m}+1\wedge a^{2^n}+1=\{\begin{array}{c}1\text{ if }a\text{ is even,}\hfill \\ 2\text{ if }a\text{ is odd.}\hfill \end{array}$$