## xᵈ-1 divides xⁿ-1 if and only if d divides n

Prove that $x^d-1$ divides $x^n-1$ if and only if $d$ divdes $n$.

Suppose $d|n$; say $n = dt$.

If $t = 1$, there is nothing to show. Suppose $t > 1$; then $x^n-1 = (x^d)^t - 1$ $= (x^d-1)(\sum_{i=0}^{t-1} (x^d)^i)$, so that $x^d-1$ divides $x^n-1$.

Now suppose $x^d-1$ divides $x^n-1$. By the Division Algorithm in $\mathbb{N}$, we have $q$ and $r$ such that $n = qd+r$. Now $x^n-1 = x^{qd}x^r - 1$ $= x^{qd}x^r -x^r + x^r - 1$ $= x^r(x^{qd}-1) + (x^r-1)$. If $q=1$, then (by the uniqueness part of the division algorithm in $\mathbb{Q}[x]$) $x^r-1 = 0$, so $r = 0$ and $d|n$. If $q > 1$, then $x^n - 1 = x^r(x^d-1)(\sum_{i=0}^{q-1} (x^d)^i) + (x^r-1)$, and again we have $r = 0$, so $d|n$.