# Thread: Messy Modular Arithmetic, I think

1. ## 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.)

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.

2. 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$