<s>[INST] If $ \gcd(a,b) = 1$ prove that $ \gcd(2a+b, a+2b) = 1$ or $3$? I have seen this question, some other related questions and answers for solving this problem. However, I tried to solve it using a different approach.
Let, $ \gcd(2a+b, a+2b) = d$
Assume $2a+b = qd\tag{1}$
and so $b = qd - 2a$
If we replace b with this in $a+2b$, we get $a+2b = 2qd - 3a$
We know, $\gcd(a,b) = 1 $. Let, $\gcd(a,qd)=m$. So $a=mn$ and $qd=lm$. In equation (1), $2a+b=qd$ or $b=qd−2a=lm−2mn=m(l−2n)$. That means $m|b$ and so $\gcd(a,b)=m$ which is not true. So, $ \gcd(a, qd) = 1$.
Thus $\gcd(2a+b,a+2b)$ = $\gcd(qd,2qd-3a)$ = $\gcd(qd,2qd-3)$. Since $\gcd(2,3) = 1, \gcd(qd,3) = 1$ or $3$ will be the answer.
Is this correct?
 [/INST] Choose integers $r,s$ such that $ar+bs=1$. Then
$$ (2a+b)(2r-s) + (a+2b)(2s-r) = 3(ar+bs) = 3. $$
So if $g=\gcd(2a+b,a+2b)$, then $g \mid 3$. Hence, $g=1$ or $3$.
Moreover, from $3 \mid \big((2a+b)+(a+2b)\big)$, we have $3 \mid (2a+b)$ if and only if $3 \mid (a+2b)$. Further, note that $3 \mid (2a+b)$ if and only if $3 \mid \big(3a-(2a+b)\big)=a-b$. Therefore,
$$ \gcd(2a+b,a+2b) = \begin{cases} 1 & \:\mbox{if}\: 3 \nmid (a-b); \\ 3 & \:\mbox{if}\: 3 \mid (a-b). \end{cases} $$
</s>