3
$\begingroup$

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!

$\endgroup$
  • 5
    $\begingroup$ It always comes down to a race of fingers with these sorts of questions... $\endgroup$ – anon Jul 21 '11 at 13:15
9
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

Alternatively, $\rm\bmod\ X+1\!:\ \ X\equiv -1\ \Rightarrow\ X^{\large \,2\,K}\equiv 1.\ $ In your case $\rm\ X = a^{\large 2^{\Large N}},\ \ 2K = 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.$

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – Carolus Jul 22 '11 at 4:30
2
$\begingroup$

See Problem $4$ in this link.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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