• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q36E

Expert-verified
Found in: Page 273

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

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

$\left({2}^{a}-1\right)mod\left({2}^{b}-1\right)={2}^{amodb}-1$

See the step by step solution

Step: 1

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

Then

${2}^{a}-{2}^{amodb}={2}^{\left(\frac{a}{b}\right)+\mathrm{madod}b}-{2}^{amodb}\phantom{\rule{0ex}{0ex}}{2}^{a}-{2}^{amodb}={2}^{modb}\left({2}^{b\left(\frac{a}{b}\right)}-1\right)$

Step: 2

${2}^{a}-{2}^{amodb}\equiv {2}^{\mathrm{amod}b}\left({2}^{b\left(\frac{a}{b}\right)}-1\right)\phantom{\rule{0ex}{0ex}}⇒\left({2}^{b\left(\frac{a}{b}\right)}-1\right)\equiv 0.\left(mod{2}^{b}-1\right)$

Step: 3

This implies that

$\left({2}^{a}-1\right)mod\left({2}^{b}-1\right)={2}^{amodb}-1$