I was self-studying Discrete Mathematics and I found the following problem.(adsbygoogle = window.adsbygoogle || []).push({});

The problem statement, all variables and given/known data

Show that wheneveraandbare 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].

Ifa = 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 withaandbdigits, respectively. Thus, these bitstrings (binary numbers) will contain only '1's as their digits.

The remainder of the division of the bitstrings consisting of onlyaandb'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 witha'1's and subtract from it the bitstring with [itex]a\mod b[/itex] '1's, the result will be a number withadigits, beginning withb'1's and ending with [itex]a\mod b[/itex] zeroes. Therefore, this result will be divisible byb, 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Question about the remainder of a division

**Physics Forums | Science Articles, Homework Help, Discussion**