# Division of $q^n-1$ by $q^m-1$, in Wedderburn's theorem

I need this for a proof of Wedderburn's theorem: $$q^m - 1 | q^n - 1 \quad \Rightarrow \quad m|n$$ with $q>1 \in \mathbf{N}$ and $m,n \in \mathbf{N}$.

I'd also like to know if it works the other way around: $$m|n \quad \Rightarrow \quad q^m - 1 | q^n - 1.$$

Thanks.

-
The other direction follows easily from the identity $(x^N - 1) = (X - 1)(X^{N - 1} + X^{N - 2} + \cdots + 1)$. – Dylan Moreland Jun 10 '12 at 19:43

Write $n=am+b$ via division algorithm: $q^m\equiv1\implies q^n-1\equiv (q^m)^aq^b-1\equiv q^b-1\bmod q^m-1$.

If this $\equiv0$ then $q^b\equiv1\Rightarrow b=0\Rightarrow m|n$. (Can't have $(q^m-1)|(q^b-1)$ otherwise; check degrees.)

For the reverse direction, apply the geometric sum formula (where $m|n$ is a given):

$$\frac{q^n-1}{q^m-1}=1+q^m+q^{2m}+\cdots+q^{n-m}.$$

-
Note this applies in the polynomial ring $\Bbb Z[x]$ rather than $\Bbb Z$. To make it applicable to an actual integer $q>1$, note that $1\le b<m$ precludes $(q^m-1)|(q^b-1)$. – anon Jun 10 '12 at 20:14

Roots of $q^n-1\in \mathbb{C}[q]$ form a group of order $n$, and the same is true for $q^m-1$.

If $q^m-1|q^n-1$ then roots of $q^m-1$ is a subgroup of roots of $q^n-1$. From Lagrange's theorem we obtain $m\;|\;n$

The inverse implication follows from the identity $$q^{mk}-1=(q^m-1)((q^m)^{k-1}+(q^m)^{k-2}+\ldots+1)$$

-
The argument with the roots of unity show that, as a polynomial, if $q^m-1\;|\;q^n-1$, then $m\;|\;n$. I don't see how it shows that there might not be some integer $q$ so that $q^m-1\;|\;q^n-1$ when $m\not|\;\;n$. – robjohn Jun 11 '12 at 0:32

Since $$\frac{a^k-1}{a-1}=\sum_{j=0}^{k-1}a^j\tag{1}$$ we immediately get that $q^m-1\;|\;q^n-1$ when $m|n$.

Now, suppose that $q^m-1\;|\;q^n-1$ and that $n=km+r$ where $0\le r< m$. Then \begin{align} \frac{q^n-1}{q^m-1} &=\frac{q^{km+r}-q^{km}}{q^m-1}+\frac{q^{km}-1}{q^m-1}\\ &=q^{km}\frac{q^r-1}{q^m-1}+\frac{q^{km}-1}{q^m-1}\\ &\in\mathbb{Z}\tag{2} \end{align} It immediately follows from $(1)$ that $\frac{q^{km}-1}{q^m-1}\in\mathbb{Z}$. Therefore, we must also have $q^{km}\frac{q^r-1}{q^m-1}\in\mathbb{Z}$: $$q^m-1\;|\;q^{km}(q^r-1)\tag{3}$$

Since $\left(q^{km},q^m-1\right)=1$, $(3)$ implies that $q^m-1\;|\;q^r-1$. However, since $0\le r< m$, we have that $0\le q^r-1< q^m-1$. Therefore, $q^r-1=0$; that is, $r=0$ and $n=km$; hence, $m|n$.

-

If $m \mid n$ then write $n=mt$ and $u=q^m$. Then $q^n-1=u^t-1=(u-1)f(u)=(q^m-1)f(q^m)$, where $f(x)=1+x+\cdots+x^{t-1}$.

-