if $d\mid n$ then $x^d-1\mid x^n-1$ proof

Question

How would you show that if $d\mid n$ then $x^d-1\mid x^n-1$ ?

My attempt :

$dq=n$ for some $q$. $$ 1+x+\cdots+x^{d-1}\mid 1+x+\cdots+x^{n-1} \tag 1$$ in fact, $$(1+x^d+x^{2d}+\cdots+x^{(q-1)d=n-d})\cdot(1+x+\cdots+x^{d-1}) = 1+x+x^2 + \cdots + x^{n-1}$$

By multiplying both sides of $(1)$ by $(x-1)$ we get that $1-x^d\mid 1-x^n$ which is the final result

Is this an ok proof?

Answer 1

An idea for you:

$$d\,\mid\,n\implies n=qd\;,\;\;q\in\Bbb Z\;,\;\;\text{and from here}: $$

$$x^n-1=\left(x^d\right)^q-1=\left(x^d-1\right)\left(\left(x^d\right)^{q-1}+\left(x^d\right)^{q-2}+\ldots+x^d+1\right)$$

The above uses the basic relation from geometric series:

$$x^a-1=(x-1)(x^{a-1}+x^{a-2}+\ldots+x+1)\;,\;\;a\in\Bbb N$$

Answer 2

Let $\alpha$ be a solution to the equation $x^d = 1$. We then have that $\alpha^d$ = 1. Since $d|n$ we can write $n = d\cdot k$ for some integer $k$. Thus $$1 = 1^k = \left( \alpha^d \right)^k = \alpha^{d\cdot k} = \alpha^n$$ This shows that $\alpha$ is a solution to $x^n = 1$.

This shows that $x^d-1|x^n-1$.

Answer 3

You can always do:

$f(y)=1+y+ \dots +y^{r-1}$ so that $yf(y)=y+y^2+\dots +y^r$ and $yf(y)-f(y)=(y-1)f(y)=y^r-1$

Then put $y=x^d$ with $dr=n$ and obtain $(x^d-1)f(x^d)=x^n-1$ and by construction $f(x^d)$ is a polynomial.

Answer 4

Hint from Dummit and Foote:

Suppose $n= kd+r$, where $0 \leq r < d$ we have $$x^n -1 = x^{kd+r} - x^r + x^r -1 = x^r (x^{kd}-1) + (x^r -1)$$ then can you conclude $d|n$ if and only if $x^d-1 | x^n-1$.

Answer 5

Notice that for any $x$ and and natural $n$ that $$(x-1)(x^{n-1} + ..... + x + 1) = (x^n + x^{n-1} +....... +x) - (x^{n-1} + x^{n-2} +.... +1) = x^n -1$$ so that $x-1|x^n - 1$ always.

Lemma: $x-1|x^n-1$ for natural $n$.

Now $d|n$ so let $m = \frac nd$ and let $y= x^d$.

Then $y-1|y^m -1$.

But $y-1 = x^d -1$ and $y^m -1 = x^n - 1$.

In particular: $(x^d -1)(x^{n-d} + x^{n-2d} + ..... + x^d + 1) = x^n - 1$

Answer 6

You have: $$d\mid n \Rightarrow n=ad$$ Then: $$x^n-1=x^{ad}-1=(x^d)^a-1$$ Setting $x^d=y$ (just for simplifying the process) we have: $$y^a-1=(y-1)(y^{a-1}+\dots+y+1)=(x^d-1)((x^d)^{a-1}+\dots + x^d+1)$$ In other words we showed that: $$x^n-1= (x^d-1)((x^d)^{a-1}+\dots + x^d+1) $$ Which obviously implies that: $$x^d-1 \mid x^n-1$$