Prove：$x^d-1 \mid x^n-1$ iff $d \mid n$.

Consider the polynomial ring $F\left[x\right]$ over a field $F$. Let $d$ and $n$ be two nonnegative integers.

Prove：$x^d-1 \mid x^n-1$ iff $d \mid n$.

my tries:

necessity, Let $n=d t+r$, $0\le r<d$

since $x^d-1 \mid x^n-1$, so,

$x^n-1=\left(x^d-1\right)\left(x^{\text{dt}+r-d}+\dots+1\right)$...

so,,, to prove $r=0$?

I don't know, and I can't go on. How to do it.

Solution 1:

Suppose $x^{d}-1\mid x^{n}-1$. By division algorithm, we can write $n=qd+r$ for some $q,r\in\mathbb{N}_0$ with $0\le r<d$. Now, observe that $$x^{d}-1 \mid (x^{d}-1)(x^{n-d}+x^{n-2d}+\cdots + x^{n-qd}+1)$$ Expanding the above, and cancelling many terms, we get that $$x^{d}-1 \mid x^{n}+x^{d}-x^{n-qd}-1=x^{n}-1+x^{d}-x^{r}$$ Together with $x^{d}-1\mid x^{n}-1$, this implies: $$x^{d}-1\mid x^{d}-x^{r}=(x^{d}-1)+(1-x^{r})$$ which gives $x^{d}-1\mid x^{r}-1$. This is a contradiction, unless $r=0$, in which case $d\mid n$.

The converse easily follows from the identity $x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+\cdots + x+1)$.

Solution 2:

Here is another take.

• $F=\mathbb Q$: Write $x^n-1 = (x^d-1)q(x)$ with $q(x) \in \mathbb Z[x]$, because $x^d-1$ is monic. Now take derivatives: $nx^{n-1} = dx^{d-1}q(x) + (x^d-1)q'(x)$. Finally, take $x=1$ to get $n=dq(1)$. Note that $q(1) \in \mathbb Z$.

• $F$ arbitrary: The $q(x) \in \mathbb Z[x]$ as above also works in $F[x]$. This is a subtle point.