# Showing that $(2^a - 1)\bmod (2^b - 1) = 2^{a \; \bmod \; b} - 1$

I've been thinking on this proof for two days. I'm stuck.

Show that, $$(2^a - 1)\bmod (2^b - 1) = 2^{a \! \! \mod b} - 1$$ where $a,b \in \mathbb{Z}^+$.

I would be happy if someone can help me.

Thanks.

-

Divide $a$ by $b$ with remainder, $a = kb + r$ with $0\leq r\lt b$. Then dividing $x^a-1$ by $x^b-1$ gives $$x^a-1 = (x^b-1)(x^{a-b} + x^{a-2b} + \cdots + x^{a-kb}) + (x^{a-kb} - 1).$$ Notice that $r=a\bmod b$ and that $a-kb = r$. Now evaluate at $x=2$, and check to make sure that everything still works out over the integers.

-
Sincere thanks to the downvoter for the insightful comments that help me understand what is not useful about this answer. –  Arturo Magidin Jan 2 '12 at 0:30

If you are working modulo $2^b-1$, you have $$2^b \equiv 1 \pmod{2^b-1}.$$

Suppose that $a=nb+c$. (That is, $a \equiv c \pmod{b}$.) Then you can simplify $$2^a = 2^{nb+c} = (2^b)^n\cdot 2^c \equiv 1^n\cdot 2^c \pmod{2^b-1}.$$

The result you are looking for follows by subtracting 1 from both sides.

-

Since $0\leq 2^{a\mod b} - 1 < 2^b - 1$, your question is equivalent to proving that $$2^a - 1 \equiv 2^{a\!\!\mod b} - 1$$ where the $\equiv$ symbol means that both sides have the same remainder when divided by $2^b-1$. This can easily be show using the properties of modulus: $$2^a -1 = 2^{a\mod b}2^{b\lfloor a/b\rfloor} - 1\equiv 2^{a\mod b}(2^{b\lfloor a/b\rfloor}\bmod (2^b-1)) - 1\equiv 2^{a\mod b} - 1$$ which works because the integers $\bmod (2^b-1)$ form what is called a "ring", allowing addition and multiplication to be performed on them. The last $\equiv$ is because $2^{b}\equiv 1$ so $2^{b\lfloor a/b\rfloor}\equiv 1^{\lfloor a/b\rfloor} \equiv 1$.

-