Prove that $(x^n - 1)$ can divide $(x^{kn} - 1)$ without any remainder.

Question

I would like your help with proving that $(x^n - 1)$ can divide $(x^{kn} - 1)$ without any remainder. I understand that both of these functions can be translated to a similar form such as $(x^2-1)=(x-1)(x+1)$. But I'm not really sure how to do so. Thank you.

Answer 1

Notice that $x^{kn} - 1 = (x^n)^k - 1.$ This implies that $x^{kn} - 1 = (x^n - 1)P(x).$

Answer 2

$$(x^n-1)|(x^{kn}-1)$$ can be written

$$(y-1)|(y^k-1).$$

Now by long division,

$$y^k-1=p(y)(y-1)+r$$ where $p$ is a polynomial and $r$ is a scalar constant (zeroth degree polynomial, if you prefer). And plugging $y=1$,

$$0=p(1)\,0+r.$$

You can conclude.

Answer 3

$x^{kn}-1=(x^n)^k-1=(x^n-1)(x^{n(k-1)}+x^{n(k-2)}+\dots+x^n+1) $