# 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
Commented Jul 21, 2011 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)\cdot(\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$$

Hint  Below put $$\rm\ X = a^{\large 2^{\Large N}}, \ 2K = 2^{M-N}\$$ (cf. coprimality of Fermat numbers)

The Factor Theorem $$\rm\, \Rightarrow\, X+1\mid X^{\large2K}-1\$$ since $$\rm\ X = -1\$$ is a root of the latter.

Alternatively $$\ \rm\bmod\ X+1\!:\ \ \color{#c00}{X\equiv -1}\, \Rightarrow\ \color{#c00}X^{\large 2K}\!\equiv (\color{#c00}{-1})^{\large2K}\!\equiv 1\,$$ via Congruence Power Rule.

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^{\large 2K}\equiv 1,\:\ 10^{2K+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". Commented Jul 22, 2011 at 4:30