# Messy Modular Arithmetic, I think

• Nov 13th 2009, 12:35 AM
Oijl
Messy Modular Arithmetic, I think
I'm sorry for the confusion, but this thread really does belong in the Discrete Mathematics, Set Theory and Logic subforum, because this problem comes from the textbook, "Discrete Mathematics and Its Applications, 6th ed." (Therefore, the methods I should use are methods taught in discrete math classes.)

I just put a bad title on the thread, I suppose. Please don't be mad at me, admins, for posting the same question twice.

This is the question:

Show that whenever a and b are both positive integers, then (2^a - 1) mod (2^b -1) = 2^(a mod b) - 1

This question is at the end of the chapter section that talks about linear congruences, the Chinese Remainder Theorem, and Fermat's Little Theorem.

Could someone point me in the right direction, please? I was thinking that I might just be able to do a sort of "modular algebra," but when I tried that, I didn't get anywhere.
• Nov 14th 2009, 09:43 PM
Haven
I'm not sure If i'm reading the question right but is it asking show that

$2^{a} - 1 ({mod}\\2^{b} - 1) = 2^{a ({mod}\\b)} - 1$

A common result from modular arithmetic is that $(2^{a}-1,2^{b}-1) = 1$ iff $(a,b)=1$ and that $2^{a}-1|2^{b}-1$ iff $a|b$