# If $m,n \in \mathbb{N}$ and $m> n$ then $(a^{2^{n}}+1)|(a^{2^{m}}-1)$ [duplicate]

Possible Duplicate:
How to show $a^{2^n}+1 \mid a^{2^m}-1$?

I am trying to solve the following question: If $m,n \in \mathbb{N}$ and $m> n$ then $(a^{2^{n}}+1)|(a^{2^{m}}-1)$, but I didn't make it.

I would appreciate any help in order to solve this question.

-

## marked as duplicate by anon, Martin Sleziak, Phira, Eric NaslundJun 10 '12 at 15:51

$a^{2^{n+1}}-1\mid a^{2^m}-1$ follows from $b\mid a$ $\Rightarrow$ $(n^b-1)\mid(n^a-1)$‌​, so it only remains to show $a^{2^n}-1\mid a^{2^{n+1}}-1$. –  Martin Sleziak Jan 29 '12 at 11:30
Almost exact duplicate: math.stackexchange.com/q/24143/6075 –  Eric Naslund Jan 29 '12 at 12:02

We can fix $n$ and show the result by induction on $m$. If $m=n+1$ then $$(a^{2^n}+1)(a^{2^n}-1)=a^{2^n+2^n}-1=a^{2^m}-1,$$ so $a^{2^n}+1\mid a^{2^m}-1$ and if it's true for a $m$ then $$a^{2^{m+1}}-1=(a^{2^m})^2-1=(a^{2^m}-1)(a^{2^m}+1)$$ and we are done, since we can write $a^{2^m}-1=k(a^{2^n}+1)$ for an integer $k$ (hence $a^{2^{m+1}}-1=k(a^{2^m}+1)(a^{2^n}+1)$.

An "other way" is to show that for $j\geq 1$: $$a^{2^{m+j}}=(a^{2^m}-1)\prod_{k=0}^{j-1}(a^{2^{m+k}}+1).$$

-

Note that :

\begin{align} 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 \\ \vdots \\ a^{2^{n+1}}-1=(a^{2^{n}}-1)(a^{2^{n}}+1) \end{align}

-

Let $m=n+b$ where $b>0$.

$$(a^{2^m}-1)=(a^{2^{n+b}}-1)=({a^{2^n}})^{2^b}-1 = c^{2^b} - 1 \text{ if } c=a^{2^n},$$ and $$(a^{2^n}+1)=c+1$$ Clearly, $$c^{2^b} - 1 \text{ is divisible by } c^2-1=(c+1)(c-1) \text{ for } b\geq 1$$

-