- #1

- 205

- 3

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

Show that whenever

[tex](2^a-1)\mod(2^b-1)=2^{a\mod b}-1[/tex]

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

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

The remainder of the division of the bitstrings consisting of only

This is true because, if we take the number with

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.

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

Last edited: