Show that $x^n -1 \mid x^k -1 \Leftrightarrow n \mid k$

Question

Problem: Show that $x^n -1 \mid x^k -1 \Leftrightarrow n \vdots k$

My solution: For the inverse statement we have $n \vdots k \Rightarrow n=kt \Rightarrow x^n = x^{kt} \Rightarrow x^n-1 = (x^k)^t-1 = (x^k-1)((x^k)^{t-1} + \dots + 1) \vdots (x^k-1)$.

How to show that the $``\Rightarrow"$ statement?

Answer 1

Here, I present a simpler proof for this question than how I originally posted:

Suppose $k = nq + r$, where $0 \leq r < n$. We have the following:

$$x^k - 1 = x^k - x^r + x^r - 1 = x^r(x^{nq} - 1) + x^r - 1$$

We know from your forward implication that $x^n - 1 \mid x^{nq} - 1$, so we have $x^n - 1 \mid x^r - 1$, which isn't true if $1 \leq r < n$, so we must have $r=0$. Therefore, $x^n - 1 \mid x^k - 1 \iff n \mid k$.

---

Here, I present my original proof for this problem:

We can use cyclotomic polynomials to prove this.

We note that $\displaystyle \prod_{d \mid n} \Phi_{d}(x) = x^n - 1$, and that every cyclotomic polynomial is irreducible.

Thus, this problem is

$$\displaystyle \prod_{d \mid n} \Phi_{d}(x) \mid \displaystyle \prod_{d \mid k} \Phi_{d}(x) \iff n \mid k$$

However, since each polynomial is irreducible, then all the terms on the LHS must be present on the RHS, so for all $d \mid n$, we must have $d \mid k$, so we must have $n \mid k$.

Answer 2

If $x^k-1$ divides $x^n-1$ then the roots $\xi_i=\exp\left(2i\pi/k\right)$ of $x^k-1$ for $i=0,\ldots,k-1$ are also roots of $x^n-1$ i.e

$$\xi_i^n=1\iff \frac nk\in \Bbb Z\iff k\vert n$$

Answer 3

Most elementary way to prove this is a following: $$x^k-1\mid x^n-1\iff x^{k-1}+...+x^2+x+1\mid x^{n-1}+...+x^2+x+1 $$ So for $x=1$ we get $$ k\mid n$$

Other way, if $k\mid n$ then $n=kl$ so $$x^n-1 = (x^k)^l-1 = (x^k-1)\Big((x^k)^{l-1}+...+x^k+1\Big)$$

so $$x^k-1\mid x^n-1$$

Answer 4

Roots of the polynomial $x^t-1$ form a finite commutative multiplicative group $G_t$. If $x^n-1$ is divided by $x^k-1$, then all the roots of the latter polynomial are the roots of the first one. In other words $G_k$ is a subgroup of $G_n$. By Lagrange's theorem $k$ divides $n$.