Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
It always comes down to a race of fingers with these sorts of questions... – anon Jul 21 '11 at 13:15
up vote 9 down vote accepted

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:


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}$.)

share|cite|improve this answer

$$(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$$

share|cite|improve this answer

See Problem $4$ in this link.

share|cite|improve this answer
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\:.$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.