Proving (2^a-1) mod (2^b-1) = 2^(a mod b)-1

[pc2-brazil]

I was self-studying Discrete Mathematics and I found the following problem.

Homework Statement
Show that whenever a and b are positive integers, then
$$(2^a-1)\mod(2^b-1)=2^{a\mod b}-1$$

The attempt at a solution
I don't know if there is a more rigorous way of solving it, but I came up with the following solution:
I will split it in three cases: $a=b$, $a<b$ and $a>b$.
If a = b, the remainder is zero, and $2^{a\mod b}-1$=$2^0-1=0$, confirming the theorem for this case.
If $a<b$:
Because $a<b$, $2^a-1<2^b-1$, therefore
$$(2^a-1)\mod(2^b-1)=2^{a}-1=2^{a\mod b}-1$$
If $a>b$:
The numbers $2^a-1$ and $2^b-1$ are the decimal equivalents of the largest binary (base 2) numbers which can be written with a and b digits, respectively. Thus, these bitstrings (binary numbers) will contain only '1's as their digits.
The remainder of the division of the bitstrings consisting of only a and b '1's, with $a>b$, will be the largest bitstring with $a\mod b$ digits (a bitstring consisting of only $a\mod b$ '1's).
This is true because, if we take the number with a '1's and subtract from it the bitstring with $a\mod b$ '1's, the result will be a number with a digits, beginning with b '1's and ending with $a\mod b$ zeroes. Therefore, this result will be divisible by b, and the remainder will be the bitstring with $a\mod b$ '1's.
So, the decimal representation of this remainder is $2^{a\mod b}-1$, confirming that
$$(2^a-1)\mod(2^b-1)=2^{a\mod b}-1$$

Is there a more rigorous way of showing this?

Thank you in advance.

 

[micromass]

Hi pc2-brazil!

I was self-studying Discrete Mathematics and I found the following problem.

Homework Statement
Show that whenever a and b are positive integers, then
$$(2^a-1)\mod(2^b-1)=2^{a\mod b}-1$$

The attempt at a solution
I don't know if there is a more rigorous way of solving it, but I came up with the following solution:
I will split it in three cases: $a=b$, $a<b$ and $a>b$.
If a = b, the remainder is zero, and $2^{a\mod b}-1$=$2^0-1=0$, confirming the theorem for this case.
If $a<b$:
Because $a<b$, $2^a-1<2^b-1$, therefore
$$(2^a-1)\mod(2^b-1)=2^{a}-1=2^{a\mod b}-1$$
If $a>b$:
The numbers $2^a-1$ and $2^b-1$ are the decimal equivalents of the largest binary (base 2) numbers which can be written with a and b digits, respectively. Thus, these bitstrings (binary numbers) will contain only '1's as their digits.
The remainder of the division of the bitstrings consisting of only a and b '1's, with $a>b$, will be the largest bitstring with $a\mod b$ digits (a bitstring consisting of only $a\mod b$ '1's).
This is true because, if we take the number with a '1's and subtract from it the bitstring with $a\mod b$ '1's, the result will be a number with a digits, beginning with b '1's and ending with $a\mod b$ zeroes. Therefore, this result will be divisible by b, and the remainder will be the bitstring with $a\mod b$ '1's.
So, the decimal representation of this remainder is $2^{a\mod b}-1$, confirming that
$$(2^a-1)\mod(2^b-1)=2^{a\mod b}-1$$

Is there a more rigorous way of showing this?

Thank you in advance.

Indeed, working with bitstrings isn't the most rigorous thing around. But there's a very easy way to make this thing rigorous. Just exchange the bitstring with a sum. For example

$$11001=2^5+2^4+1~\text{and}~111111=2^6+2^5+2^4+2^3+2^2+2+1$$

So just exchange each occurrence of the bitstring with such a sum.