- #1
pc2-brazil
- 205
- 3
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.
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: