number theory - Show that $(2^p-1,2^{q-1}-1)=2^{(p,q-1)}-1$

Let $p$ and $q$ are two prime numbers. Also, let us assume $q|(2^p-1)$. Then show that $(2^p-1,2^{q-1}-1)=2^{(p,q-1)}-1$. Note- $(p,q)$ denotes HCF of $p$ and $q$.

Answer

It's true in general that

$$\left (2^a-1,2^b-1 \right )=2^{(a,b)}-1$$ for $a$ , $b$ positive integers .

My favorite proof goes as follows :

Perform an induction on $a+b$ :

• The base case $a+b=2$ so $a=b=1$ it's obvious .




• Now assume that it's true for all $a$ and $b$ with $a+b \leq k$ .

Take some $a$ and $b$ with $a+b=k+1$ . Let also $d=\left (2^a-1,2^b-1 \right )$

Clearly $d$ is odd and also :

$$d \mid (2^a-1)-(2^b-1)=2^b(2^{a-b}-1)$$ (assuming $a \geq b$) so :

$$d \mid 2^{a-b}-1$$

This means that :

$$d \mid (2^b-1,2^{a-b}-1)$$

But because $b+a-b=a \leq k$ it folows that the RHS is $2^{(b,a-b)}-1$

Also it's clear that $(b,a-b)=(a,b)$ so :

$$d \mid 2^{(a,b)}-1$$

But also

$$2^{(a,b)}-1 \mid d$$ because :
$$2^{(a,b)}-1 \mid 2^a-1$$ and also :

$$2^{(a,b)}-1 \mid 2^b-1$$

This means that $d=2^{(a,b)}-1$ and the induction is finished :

NOTE : This is essentially equivalent with a proof using the Euclidean algorithm .