Dismiss Notice
Join Physics Forums Today!
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

  1. Aug 7, 2011 #1
    I was self-studying Discrete Mathematics and I found the following problem.

    The problem statement, all variables and given/known data
    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: Aug 7, 2011
  2. jcsd
  3. Aug 7, 2011 #2
    Hi pc2-brazil! :smile:

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook