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

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.

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.