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