Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer
Thanks, I'm studying it. – BeetleTheNeato Apr 23 '13 at 18:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.