Question

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$

Short answer

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

Step-by-step solution

Step: 1

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

Then

$$\begin{gathered} 2^a-2^{amodb}=2^{\left(\frac{a}{b}\right)+\mathrm{madod}b}-2^{amodb} \\ {2}^a-2^{amodb}=2^{modb}\left(2^{b\left(\frac{a}{b}\right)}-1\right) \end{gathered}$$

Step: 2

$$\begin{gathered} 2^a-2^{amodb}\equiv 2^{\mathrm{amod}b}\left(2^{b\left(\frac{a}{b}\right)}-1\right) \\ \Rightarrow \left(2^{b\left(\frac{a}{b}\right)}-1\right)\equiv 0.\left(mod{2}^b-1\right) \end{gathered}$$

Step: 3

This implies that

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