Prove gcd is one of the following {1, 3}

Question

Prove that if $\gcd(a, b) = 1$ then $\gcd(2a + b, a + 2b) \in \{1, 3\}$

I can get up to: $\gcd(2a + b, a + 2b) | 3(a + b)$

But I am unable to move forwards. I would like a hint?

BY Bezout's, there exists integers $x, y$ such that $ax + by = 1$.

$d = \gcd(2a + b, a + 2b) \implies (2a + b)u + (a + 2b)t = d$ for integers existing $u, t$.

But this isn't helping much. What can I do?

Answer 1

Hint:

Let $d=(a+2b,2a+b)$, so $d|3a$ since $d|2(2a+b)-(a+2b)$ and $d|3b$ since $d|2(a+2b)-(2a+b)$.

Therefore $d|(3a,3b)$.

Answer 2

You find that $\gcd (2a+b,a+2b) \mid 3(a+b)$. You also have $\gcd (2a+b,a+2b) \mid 3(2a+b)$ so $\gcd (2a+b,a+2b) \mid 3(2a+b)-3(a+b)=3b$. Then use $\gcd (a,b)=1$ to follow $\gcd (2a+b,a+2b) \mid 3$.