show that the remainder upon dividing $a^n-1$ by $a^m-1$ is $a^r-1$

Question

If $n=qm+r, \ 0 \leq r <m$, then show that the remainder upon dividing $a^n-1$ by $a^m-1$ is $a^r-1$.

Answer:

If $q$ is a positive integer, then $a^{m}$ divides $\large a^{qm}-1$. For,

$a^{qm}-1=(a^m-1)(1+a^m+a^{2m}+ \cdots +a^{m(q-1})$.

But I can not finish the problem.

Help me.

Answer 1

Hint: If $n=qm+r$, then $a^n-1 = a^r(a^{qm} - 1) + (a^r - 1)$.

Answer 2

$\bmod\, \color{#c00}{a^{\large m}\!-\!1}\!:\,\ a^{\large r+mq}\!= a^{\large r} (\color{#c00}{a^{\large m}})^{\large q}\!\equiv a^{\large r} \color{#c00}1^{q}\!\equiv a^{\large r}$

i.e. if $\ a^{\large m}\equiv 1$ then $\, a^{\large n}\!\equiv a^{\large n\bmod m},\,$ i.e. $ $ expts on $\,a\,$ can be reduced $\!\bmod m$