Question

a) If and are positive integers, prove that the least residue of ${\mathbf{2}}^{\mathbf{a}}\mathbf{-}\mathbf{1}$modulo${\mathbf{2}}^{\mathbf{b}}\mathbf{-}\mathbf{1}$ is${\mathbf{2}}^{\mathbf{r}}\mathbf{-}\mathbf{1}$ , where r is the least residue of b .
b) If a and b are positive integers, prove that the greatest common divisor ofrole="math" localid="1659180724078" ${\mathbf{2}}^{\mathbf{a}}\mathbf{-}\mathbf{1}$ and ${\mathbf{2}}^{\mathbf{b}}\mathbf{-}\mathbf{1}$is ${\mathbf{2}}^{\mathbf{t}}\mathbf{-}\mathbf{1}$, whereis the gcd ofand. [Hint: Use the Euclidean Algorithm and part (a).]
c) Let and be positive integers. Prove that${\mathbf{2}}^{\mathbf{a}}\mathbf{-}\mathbf{1}$ and${\mathbf{2}}^{\mathbf{b}}\mathbf{-}\mathbf{1}$ are relatively prime if and only if and are relatively prime.

Short answer

1. Least residue of $2^a-1$modulo $2^b-1$is $2^r-1$
2. Greatest common divisor of $2^a-1$and $2^b-1$is$2^t-1$
3. $2^a-1$and $2^b-1$are relatively prime if and only if a and b are relatively prime.

Step-by-step solution

(a) Find least residue

We have, residue of is r

$$\begin{gathered} a=rmodb \\ a=r+qb \end{gathered}$$

Write the expression for 2a-1

We write given expression,

$$\begin{gathered} 2^a-1=2^{r+qb}-1 \\ =2^r{2}^{qb}-2^r+2^r-1 \\ =2^r-1+Q{2}^b-Q \\ {2}^a-1=\left(2^r-1\right)+Q\left(2^b-1\right) \end{gathered}$$

Hence, least residue of $2^a-1$modulo $2^b-1$is$2^r-1$

(b) Write the equation for t

We write given GCD as,

$t=\left(a,b\right)$

Hence, we can write

$$\begin{gathered} t=pa+qb \\ {2}^t-1=2^{pa+qb}-1 \end{gathered}$$

$=r\left(2^a-1\right)+S\left(2^b-1\right)$

GCD of $\left(2^a-1\right)$and $\left(2^b-1\right)$is$2^t-1$

(c) Write the equation for  2a-1and 2b-1

We write given GCD

$1=\left(2^a-1,2^b-1\right)$

Hence, we can write

$1=r\left(2^a-1\right)+s\left(2^b-1\right)$

We write the equation further as

$1=ax+by$

Thus, are relatively prime