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

I've been struggling with this all day today. I imagine it's not very hard, but my algebra skills are terrible. So, how can I show that if $m>n$ and $a$ is a positive integer, then $$a^{2^n}+1 \mid a^{2^m}-1.$$ I just can't get a coherent picture of what I'm supposed to do. If this too (see yesterday's question) boils down to the Unique Factorization Theorem, I would be very grateful for any intuition on how to think about this!

-
It always comes down to a race of fingers with these sorts of questions... – anon Jul 21 '11 at 13:15

First you could try to show that: $x-1\mid x^k-1$ for any integer $x$ and any positive integer $k\ge 1$. (This follows from the well-known equality $x^k-1=(x-1).(\ldots)$; try to fill in the dots.)

Now you can use:

$(a^{2^n}-1)(a^{2^n}+1)=(a^{2^n})^2-1=a^{2^{n+1}}-1$

This means that $a^{2^n}+1 \mid a^{2^{n+1}}-1$ and using the above result for $x=a^{2^{n+1}}$ and $k=2^{m-(n+1)}$ you get $a^{2^{n+1}}-1\mid a^{2^m}-1$.

(Note that $(a^{2^{n+1}})^{2^{m-(n+1)}} = a^{2^{n+1}.2^{m-(n+1)}} = a^{2^m}$.)

-

$$(a^{2^n}+1)(a^{2^n}-1)(a^{2^{n+1}}+1)(a^{2^{n+2}}+1)\cdots(a^{2^{m-1}}+1) = a^{2^m}-1$$

-

See Problem $4$ in this link.

-
Thanks for the link, good to have! – Carolus Jul 21 '11 at 13:18
@Carolus: Thanks. Credit must be given to $\mathsf{Google}$ though. :) – user9413 Jul 21 '11 at 13:18
I actually did google it, hmm... I better get my eyes checked :/ – Carolus Jul 21 '11 at 13:21

HINT $\$ The Factor Theorem $\rm\: \Rightarrow\ X+1\ |\ X^{\:2\:K}-1\$ since $\rm\ X = -1\$ is a root of the latter.

Alternatively, $\rm\ mod\ X+1:\ \ X\equiv -1\ \Rightarrow\ X^{\:2\:K}\equiv 1\:.\$ In your case $\rm\ X = a^{2^N},\ \ 2\:K = 2^{\:M-N}.$

Note in particular how the use of modular arithmetic enables one to reduce the proof to the triviality that $\rm\ (-1)^2 = 1\:.\:$ Such order $2$ cyclicity is ubiquitous, e.g. the test for divisibility by $11\:,\$ where $\rm\ 10\equiv -1\ \Rightarrow\ 10^{\:2\:K}\equiv 1,\:\ 10^{\:2\:K+1}\equiv -1\:.$

-
Thanks for the added explanation! By the way, do you have any tips for getting a better grasp of algebraic manipulations? I sometimes (often) have difficulties seeing "the next natural step". – Carolus Jul 22 '11 at 4:30