183k views
4 votes
Show that if a and b are both positive integers, then (2^a − 1) mod (2^b − 1) = 2^(a mod b) − 1

1 Answer

6 votes

Final answer:

To prove that (2^a − 1) mod (2^b − 1) = 2^(a mod b) - 1, we use properties of exponents and modular arithmetic to show that only the remainder, or 2^(a mod b), contributes to the final result after taking the modulus with (2^b − 1).

Step-by-step explanation:

To show that for positive integers a and b, the expression (2a − 1) mod (2b − 1) equals 2(a mod b) − 1, we can apply the properties of exponents and modular arithmetic. Recall that a mod b is the remainder when a is divided by b. If we let a = qb + r, where q is the quotient and r is the remainder (r = a mod b), then 2a can be expressed as 2(qb + r), which equals 2qb2r by the exponentiation rule.

Since 2b − 1 divides evenly into 2qb − 1 (as 2qb is just (2b)q, i.e., a power of 2b), we can say any power of 2qb will reduce to some remainder when divided by 2b − 1. Thus, (2a − 1) mod (2b − 1) simplifies to (2(qb + r) − 1) mod (2b − 1), which is just (2qb2r − 1) mod (2b − 1). Because the term 2qb contributes no remainder, we only need to consider 2r − 1, thus arriving at the desired result: 2(a mod b) − 1.

User William Stein
by
9.0k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories