Prove: For $m,n,a \in \mathbb{Z+}$, if $m \gt n$, then $a^{2^n} +1 \mid a^{2^m} -1$

Question

Trying out a few examples, let (i) $a=3, n=1, m=2, 3^2+1=10, 3^4-1=80, 10\mid 80$, (ii) $a=3, n=2, m=3, 3^4+1=82, 3^8-1=6560, \frac{6560}{82}= 80$.

To derive a proof, should derive $a^{2^n} +1$ as a factor of $a^{2^m} -1$, & as $m\gt n$, so $a^{2^m}=a^{2^n}.a^{2^{(n-m)}}$, so $a^{2^m}-1=a^{2^n}.a^{2^{(n-m)}}-1$.

It is possible to state the next step, based on something like $a^2-1=(a-1)(a+1)$, but lack familiarity with such type of polynomial (if chosen the correct word) division.

Also, would request a generalized answer, for different bases for powers of $n,m$.

Answer 1

Hints (either of the following):

• $a^{2^{m}} - 1 = \left(a^{2^{m-1}} - 1\right)\left(a^{2^{m-1}} + 1\right)$ , so $\,a^{2^{m-1}} - 1 \mid a^{2^m} - 1 \,$, then $\,a^{2^{n}} - 1 \mid a^{2^m} - 1 \,$ for $\,n \lt m\,$ by induction

• let $\,N=\left(a^{2^{n}} + 1\right)\left(a^{2^{n+1}} + 1\right)\ldots\left(a^{2^{m-1}} + 1\right)\,$, then telescoping $\,(x-1)(x+1)=x^2-1\,$:

$$ \begin{align} \left(a^{2^{n}} - 1\right)N &= \left(a^{2^{n}} - 1\right)\left(a^{2^{n}} + 1\right)\left(a^{2^{n+1}} + 1\right)\ldots\left(a^{2^{m-1}} + 1\right) \\ &= \left(a^{2^{n+1}} - 1\right)\left(a^{2^{n+1}} + 1\right)\ldots\left(a^{2^{m-1}} + 1\right) \\ &= \cdots \\ &= \left(a^{2^{m-1}} - 1\right)\left(a^{2^{m-1}} + 1\right) \\ &= \left(a^{2^{m}} - 1\right) \end{align} $$

Answer 2

\begin{eqnarray*} a^{2^{m}}-1 &=& (a^{2^{m-1}}+1)(a^{2^{m-1}}-1) \\ &=& (a^{2^{m-1}}+1)(a^{2^{m-2}}+1)(a^{2^{m-2}}-1) \\ & & \vdots \\ &=& (a^{2^{m-1}}+1)(a^{2^{m-2}}+1)\cdots \color{red}{(a^{2^{n}}+1)}\cdots (a^2+1)(a+1)(a-1). \end{eqnarray*}