StudySmarter AI is coming soon!

:00Days
:00Hours
:00Mins
00Seconds

A new era for learning is coming soonSign up for free

Log In Start studying!

Select your language

Suggested languages for you:

Deutsch (DE)

Deutsch (UK)

Deutsch (US)

Americas

English (US)

Europe

Q36E

Expert-verified

Discrete Mathematics and its Applications

Found in: Page 273

Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Register for Free I’ll do it later

Short Answer

Show that if a and b are both positive integers, then $(2^{a} - 1) mod (2^{b} - 1) = 2^{a mod b} - 1$

$(2^{a} - 1) mod (2^{b} - 1) = 2^{a mod b} - 1$

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step: 1

The value a, can be written as $a = b (\frac{a}{b}) + (a mod b)$

Then

$2^{a} - 2^{a mod b} = 2^{(\frac{a}{b}) + madod b} - 2^{a mod b} 2^{a} - 2^{a mod b} = 2^{mod b} (2^{b (\frac{a}{b})} - 1)$

Step: 2

$2^{a} - 2^{a mod b} \equiv 2^{amod b} (2^{b (\frac{a}{b})} - 1) \Rightarrow (2^{b (\frac{a}{b})} - 1) \equiv 0 . (mod 2^{b} - 1)$

Step: 3

This implies that

$(2^{a} - 1) mod (2^{b} - 1) = 2^{a mod b} - 1$

Most popular questions for Math Textbooks

Convert $(1101100101011011)_{2}$ to octal and hexadecimal representations.

Prove that there are no solutions in integers x and y to the equation $x^{2} - 5 y^{2} = 2$ .[Hint: Consider this equation modulo 5 .]

a) Define what it means for a and b to be congruent m odulo 7.

b) Which pairs of the integers -11,-8,-7,-1,0,3 and 17 are congruent ?

c) Show that if a and b are congruent m odulo 7, then 10a+13 and -4b+20 are also congruent m odulo 7.

Convert (ABCDEF)16 from its hexadecimal expansion to

its binary expansion.

It can be shown that every integer can be uniquely represented in the form

$3^{k} + e_{k - 1} 3^{k - 1} + L + e_{1} 3 + e^{j}$

where $e_{j} = - 1, 0$ , or 1 for j=0,1,2, …., k. Expansions of this type are called balanced ternary expansions. Find the balanced ternary expansions of

a) 5 .

b) 13 .

c) 37 .

d) 79 .

Want to see more solutions like these?

Sign up for free to discover our expert answers

Get Started - It’s free

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.

Sign up for free

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Show that if a and b are both positive integers, then $(2^{a} - 1) mod (2^{b} - 1) = 2^{a mod b} - 1$

Step by Step Solution

Step: 1

Step: 2

Step: 3

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Show that if a and b are both positive integers, then 2a−1mod2b−1=2amodb−1

Step by Step Solution

Step: 1

Step: 2

Step: 3

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths

Show that if a and b are both positive integers, then $(2^{a} - 1) mod (2^{b} - 1) = 2^{a mod b} - 1$