1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    So just exchange each occurence of the bitstring with such a sum.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook