Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
5  
It always comes down to a race of fingers with these sorts of questions... –  anon Jul 21 '11 at 13:15
add comment

4 Answers

up vote 8 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:

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

share|improve this answer
add comment

$$(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|improve this answer
add comment

See Problem $4$ in this link.

share|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
add comment

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|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
add comment

Your Answer

 
discard

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.