# Proof involving division algorithm

I'm trying to prove the following.

Let $m$ and $n$ be positive integers, $n>m$. Prove that if $n$ divided by $m$ leaves remainder $r$, then $2^n - 1$ divided by $2^m-1$ leaves remainder $2^r-1$.

So I wrote:

$$n = mq_1 + r \Rightarrow 2^n-1 = (2^m-1)q_2 + r'$$

I was trying to manipulate the sentence on the right to get $r'=2^r-1$. Is this a good path? Then I substituted $n$ for $mq_1+r$, since that's the hypothesis. Like this:

$$r' = 2^{mq_1+r} -1 - q_2(2^m-1)$$ $$r'= 2^{mq_1}2^r - 1 - q_2(2^m - 1)$$ $$r'=(2^m)^{q_1}2^r - 1 - q_2(2^m - 1)$$

Anyway, that didn't help much. At some point I'll have to deal with $q_1$ and $q_2$, but I don't know how. I noticed that, since $r$ is the remainder, $n \gt m \gt r$. But is that useful?

Can you please help me? I'm having a hard time in my undergraduate classes of Algebra. I know all the properties but I can't seem to use them to get somewhere, i.e., I usually can't use them to prove anything. The teacher is already talking about prime numbers, but I'm still struggling to understand the first lessons on division algorithm and divisibility.

-

Hint $\rm\ \ a^n\!-\!1\ =\ a^{n-m} \: (a^m\!-\!1) + a^{n-m}\!-\!1.\$ See here for much more.