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
[tex](2^a-1)\mod(2^b-1)=2^{a\mod b}-1[/tex]

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: [itex]a=b[/itex], [itex]a<b[/itex] and [itex]a>b[/itex].
If a = b, the remainder is zero, and [itex]2^{a\mod b}-1[/itex]=[itex]2^0-1=0[/itex], confirming the theorem for this case.
If [itex]a<b[/itex]:
Because [itex]a<b[/itex], [itex]2^a-1<2^b-1[/itex], therefore
[tex](2^a-1)\mod(2^b-1)=2^{a}-1=2^{a\mod b}-1[/tex]
If [itex]a>b[/itex]:
The numbers [itex]2^a-1[/itex] and [itex]2^b-1[/itex] 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 [itex]a>b[/itex], will be the largest bitstring with [itex]a\mod b[/itex] digits (a bitstring consisting of only [itex]a\mod b[/itex] '1's).
This is true because, if we take the number with a '1's and subtract from it the bitstring with [itex]a\mod b[/itex] '1's, the result will be a number with a digits, beginning with b '1's and ending with [itex]a\mod b[/itex] zeroes. Therefore, this result will be divisible by b, and the remainder will be the bitstring with [itex]a\mod b[/itex] '1's.
So, the decimal representation of this remainder is [itex]2^{a\mod b}-1[/itex], confirming that
[tex](2^a-1)\mod(2^b-1)=2^{a\mod b}-1[/tex]

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
[tex](2^a-1)\mod(2^b-1)=2^{a\mod b}-1[/tex]

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: [itex]a=b[/itex], [itex]a<b[/itex] and [itex]a>b[/itex].
If a = b, the remainder is zero, and [itex]2^{a\mod b}-1[/itex]=[itex]2^0-1=0[/itex], confirming the theorem for this case.
If [itex]a<b[/itex]:
Because [itex]a<b[/itex], [itex]2^a-1<2^b-1[/itex], therefore
[tex](2^a-1)\mod(2^b-1)=2^{a}-1=2^{a\mod b}-1[/tex]
If [itex]a>b[/itex]:
The numbers [itex]2^a-1[/itex] and [itex]2^b-1[/itex] 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 [itex]a>b[/itex], will be the largest bitstring with [itex]a\mod b[/itex] digits (a bitstring consisting of only [itex]a\mod b[/itex] '1's).
This is true because, if we take the number with a '1's and subtract from it the bitstring with [itex]a\mod b[/itex] '1's, the result will be a number with a digits, beginning with b '1's and ending with [itex]a\mod b[/itex] zeroes. Therefore, this result will be divisible by b, and the remainder will be the bitstring with [itex]a\mod b[/itex] '1's.
So, the decimal representation of this remainder is [itex]2^{a\mod b}-1[/itex], confirming that
[tex](2^a-1)\mod(2^b-1)=2^{a\mod b}-1[/tex]

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

[tex]11001=2^5+2^4+1~\text{and}~111111=2^6+2^5+2^4+2^3+2^2+2+1[/tex]

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