Prove $q^m -1 \mid q^n-1$ implies $m\mid n$ I'm reading a proof, in which they claim:
$q^m -1 \mid q^n-1$ implies $m\mid n$
They continue by substituting $n = am +r$ for $0 \leq r < m$, then saying $q^m-1\mid q^{am+r} -1$ implies:
$q^m-1\mid (q^{am+r} -1)-(q^m-1) = q^m(q^{(a-1)m+r}-1)$
and thus $q^m-1\mid q^{(a-1)m+r} -1$ since $q^m$ and $q^m-1$ are relatively prime. Continuing in this way we find $q^m-1\mid q^r-1$ which is only possible for $r = 0$, that is, $m\mid n$.
I am not quite following this, what is the purpose of subtracting $q^m-1$ and why does that help prove the claim?
 A: This is the standard proof of the fact. Basically suppose the opposite: $q^m-1$ divides $q^n-1$ but $m$ does not divide $n$. And assume that $n$ is the smallest possible for this $m$. Then first,
$n>m$ otherwise $q^n-1\le q^m-1$.
Second, divide $m$ by $n$ with a remainder as in your question, etc. and produce smaller $n$ for the same $m$, a contradiction.  Subtracting $q^m-1$ is just a trick to achieve this goal. There is no deep meaning here.
A: 
what is the purpose of subtracting $q^m−1$ and why does that help prove the claim?

There are deeper algebraic reasons behind this (that will become apparent once one studies ideal theory or cyclic groups). I will try to explain the gist of it without requiring any knowledge of such.
The descent in the induction is: $ $ if $\, q^n-1$ is a multiple of $\,q^m-1$ then so too is $\,q^{n-m}-1,\,$ i.e. we descend from expt $\,n\,$ to $\,n-m,\,$ when $\,n\ge m.\,$ Iterating, we continue subtracting $m$ till we reach $\,r := n\bmod m = $ least nonnegative value of $\,n-km.\,$ Abstracting a bit, this is a special case of
Lemma $ $ If a set $S$ of naturals is $\rm\color{#c00}{closed}$  under subtraction $(>0)$ then it is closed under remainder (mod), by remainder is computable by iterated subtraction $\,n\bmod m = ((n\! -\! m)\! -\! m)\cdots -m $
Let $\,S\,$ be the set of naturals $k>0$ with $\,q^m-1\mid q^k-1$. Then $m\in S$ and $\,n\in S$ by hypothesis, hence $\,n\bmod m = r\in S\,$ by the Lemma, so $\,q^m-1\mid q^r-1,\,$ once we verify $S$ is $\rm\color{#c00}{closed}$ under subtraction $(> 0)$ as follows: $\,j> k\in S$ means $q^m-1$ divides $q^j-1,q^k-1\,$ so it divides their difference $\,\color{#0a0}{q^k}(q^{j-k}-1),\,$ so also $q^{j-k}-1$ (so $\,\color{#c00}{j\!-\!k\in S})$, by Euclid & $\,\gcd(\color{#0a0}q,q^m-1)\!=\!1$.
The OP quoted proof essentially works the same as above but omits explicitly highlighting the innate algebraic structure of the set $S$ - that it is closed closed under subtraction $(>0).$ When extended from $\Bbb N$ to $\Bbb Z$  such subtraction closed sets are prototypical examples of fundamental algebraic structures that are ubiquitous in number theory and algebra - namely subgroups of cyclic groups and (principal) ideals in (Euclidean) rings.
Notice, further, the fact that $S$ is closed under mod shows that $S$ is also closed under gcd (since Euclid's algorithm just iterates mods). The above use of subtraction (vs. mod) corresponds to using the subtractive version of the Euclidean algorithm: $\, m>n\Rightarrow \gcd(m,n) = \gcd(m-n,n).\,$
Now we can use either of these descent methods to then prove a key structural result about $\,S,\,$ namely $\,q^k\equiv 1 \iff m\mid k,\,$ where $k=m$ is the least natural with $\,q^k\equiv 1,\,$ i.e. the order of $q$.
These are special cases of basic results presented in courses in abstract algebra and number theory on cyclic groups and ideals (which are principal in a Euclidean domain, generated by their least nonzero element). For further discussion see here.
See also this answer which briefly explains the innate exponential $q$-analogy, namely that $\,a_m = q^m-1\,$ satisfies $\,a_m\mid a_n\iff m\mid n,\,$ and $\,\gcd(a_m,a_n) = a_{\gcd(m,n)},\,$ i.e. $\,a_k\,$ is a strong divisibility sequence.
A: Given that $q^{m}-1 \mid q^{n}-1$, we have $n\geq m.$
Assume, on the contrary, that $m\not |n$, then by the Euclidean Algorithm, $$
n=pm +r \text { for some }p\in N, \text{and } 0<r<m \cdots (*).
$$
We have $$
q^{n}-1 =\left(q^{n-m}+q^{n-2 m}+\cdots+q^{n-p m}\right)\left(q^{m}-1\right)+\left(q^{r}-1\right)
$$
$$\therefore q^{m}-1 \mid q^{n}-1 \Rightarrow q^{m}-1 \mid q^{r}-1 \Rightarrow m\leq r, \textrm{ which contradicts to the condition (*)}.$$
Now we can conclude that $m|n.$
