Let $m$ and $n$ be relatively prime positive integers. Determine all possible values of

$$
\operatorname{gcd}\left(2^{m}-2^{n}, 2^{m^{2}+m n+n^{2}}-1\right) .
$$

Answer: 1 and 7 .
Without restriction of generality we may assume that $m \geqslant n$. It is well known that

$$
\operatorname{gcd}\left(2^{p}-1,2^{q}-1\right)=2^{\operatorname{gcd}(p, q)}-1,
$$

SO

$$
\begin{aligned}
\operatorname{gcd}\left(2^{m}-2^{n}, 2^{m^{2}+m n+n^{2}}-1\right) & =\operatorname{gcd}\left(2^{m-n}-1,2^{m^{2}+m n+n^{2}}-1\right) \\
& =2^{\operatorname{gcd}\left(m-n, m^{2}+m n+n^{2}\right)}-1 .
\end{aligned}
$$

Let $d \geqslant 1$ be a divisor of $m-n$. Clearly, $\operatorname{gcd}(m, d)=1$, since $m$ and $n$ are relatively prime. Assume that $d$ also divides $m^{2}+m n+n^{2}$. Then $d$ divides $3 m^{2}$. In view of $\operatorname{gcd}(m, d)=1$ the only choices for $d$ are $d=1$ and $d=3$. Hence $\operatorname{gcd}\left(m-n, m^{2}+m n+n^{2}\right)$ is either 1 or 3 . Consequently, $\operatorname{gcd}\left(2^{m}-2^{n}, 2^{m^{2}+m n+n^{2}}-1\right)$ may only assume the values $2^{1}-1=1$ and $2^{3}-1=7$.

Both values are attainable, since $m=2, n=1$ gives

$$
\operatorname{gcd}\left(2^{2}-2^{1}, 2^{2^{2}+2 \cdot 1+1^{2}}-1\right)=\operatorname{gcd}\left(2,2^{7}-1\right)=1
$$

whereas $m=1, n=1$ gives

$$
\operatorname{gcd}\left(2^{1}-2^{1}, 2^{1^{2}+1 \cdot 1+1^{2}}-1\right)=\operatorname{gcd}\left(0,2^{3}-1\right)=7
$$

#