Question about the remainder of a division

[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 occurence of the bitstring with such a sum.