Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer

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

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

Your Answer

 
discard

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.