StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q36E

Expert-verifiedFound in: Page 273

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$

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

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)$

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

This implies that

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

94% of StudySmarter users get better grades.

Sign up for free