Claim: if $a, m, n$ are positive integers with $a>1$, then $a^m-1 \mid a^n-1$ if and only if $m \mid n$. I need the only if, or forward direction, of this proof. Explanation would also be helpful. I believe the solution involves the division algorithm.
Claim: if $a, m, n$ are positive integers with $a > 1$, Then $a^m - 1 \mid a^n - 1$ if and only if $m \mid n$.
 A: Well, let's roll up our sleeves.
If you divide $a^m-1$ into $a^n-1$, assuming $m < n$ you get
$a^n -1 = (a^m-1)a^{n-m} + a^{n-m} -1$.
Then, assuming $n-m > m$, we get
$a^n-1 = (a^m -1)a^{n-m} + (a^m -1)a^{n-2m} + a^{n-2m} -1$.
So thinking about what this implies inductively:
If $n = qm + r$ then 
If $q > 0$ then
$a^n - 1 = (a^m - 1)(a^{n-m} + a^{n-2m} + ....... + a^{n- qm}) + a^{n-qm} - 1$
(Just expand that out.  You'll see it is so)
And $n-qm < m$ so $a^{n-qm} < a^m -1$.  So $0 \le a^{n-qm} - 1 < a^m -1$.
So $a^{n-qm} - 1$ is a remainder.
So $a^m - 1|a^n-1$ if and only if $a^{n-qm} - 1 =0$ if and only if $n = qm$.
...
And if $q = 0$ then $m \ge n$ and $a^m - 1 \ge a^n-1$ so $a^m - 1|a^n -1$ if and only if $a^m-1 = a^n-1$ if and only if $n = m$.
So that's a full proof.
A: Hint: Let $n = km +r$, with $0\le k<m$, then
$$ \begin{aligned}a^n - 1 &= a^{km + r} - a^r + a^r -1\\
&= a^r\left( (a^m)^k -1 \right) + a^r-1\\
&= a^r(a^m-1)\left( (a^m)^{k-1}+\cdots + 1\right) + a^r -1.
\end{aligned}$$
A: For one direction, if $m|n$ let $n=mr$ with $r\in \Bbb N,$ and let $a^m=x.$ Then $a^m-1=x-1$ and $a^n-1=x^r-1=(x-1)s=(a^m-1)s,$ where $s=\sum_{j=0}^{r-1}x^j\in \Bbb N.$
For the other direction, if $m\not |\; n,$ then: 
(i). If $m>n$ then $a^m-1>a^n-1>0$ so (obviously) $
\;a^m-1 \not | \;a^n-1.$ 
(ii). If $m<n$ let $n=my+z$ where $y,z\in \Bbb N$ and $z<m.$   Then $a^m\equiv 1 \mod {a^m-1}.$ So modulo $a^m-1$ we have $$a^n-1\equiv a^{my+z}-1\equiv (a^m)^ya^z-1\equiv 1^ya^z-1\equiv a^z-1.$$ But since $0<a^z-1<a^m-1,$ we  have $a^z-1\not \equiv 0 \mod {a^m-1}.$ So $a^n-1\not \equiv 0\mod {a^m-1}.$ 
A: 
This should be correct. Uses algebra to solve.
