-1
$\begingroup$

I found this in some notes from a course in number theory. How do i work to solve this?

$\endgroup$
  • $\begingroup$ Write $x^{2^k}=y$. Can you show that $y+1\mid y^2-1\mid y^{2^{\ell-k}}-1$? $\endgroup$ – Jyrki Lahtonen Apr 17 '19 at 17:15
  • $\begingroup$ Meaning that the question is reduced to this near duplicate. $\endgroup$ – Jyrki Lahtonen Apr 17 '19 at 17:22
  • $\begingroup$ Also, I highly recommend that you take a look at our guide for new askers. The question is a bit lacking in the context department. If you could convince us that you are not just trying to get somebody to do your homework we would feel a lot better about the question. $\endgroup$ – Jyrki Lahtonen Apr 17 '19 at 17:24
4
$\begingroup$

$$x^{2^l}-1=(x^{2^{l-1}}+1)(x^{2^{l-1}}-1)$$ Continue to expand the right hand factor until you get $$x^{2^l}-1=(x-1)\prod_{k=0}^{l-1} \left(x^{2^k}+1\right)$$ Which is obviously divisible by $x^{2^k}+1$ for all $0\le k\lt l$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$\bmod\, x^{\large 2^{\Large K}}\!\!+1\!:\ \ \color{#c00}{x^{\large 2^{\Large K}}\!\!\equiv -1}\,\Rightarrow\, x^{\large 2^{\Large K+N}}\!\!\equiv (\color{#c00}{x^{\large 2^{\Large K}}})^{\large 2^{\Large N}}\!\!\equiv (\color{#c00}{-1})^{\large 2^{\Large N}}\!\!\equiv 1\ $ $\!\!\overbrace{{\rm when} \ \ N> 0}^{\large K\, <\, K+N\, =:\, L_{\phantom{I_I}}}$


Remark $ $ It's a special case of $\ x^{\large K}\!+1\mid x^{\large 2K}\!-1\mid x^{\large 2KN}\!-1,\,$ also provable by mod

$\bmod\, x^{\large K}\!+1\!:\ \ \color{#c00}{x^{\large K} \!\!\equiv -1}\,\Rightarrow\, x^{\large 2KN} \!\equiv (\color{#c00}{x^{\large K}})^{\large 2N}\!\equiv (\color{#c00}{-1})^{\large 2N}\!\equiv 1\ $

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ If you learn to reason by $\!\bmod$ as above then you don't have to remember motley divisibility formulas - they occur very naturally as special cases of general results (e.g. abobe that $\,(-1)^{2N} = 1)\ \ $ $\endgroup$ – Gone Apr 17 '19 at 17:40

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