# Prove gcd is one of the following {1, 3} [duplicate]

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?

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)$.

• How does $d|3a$ and $d|3b$ lead to the conclusion that $d|(3a, 3b)$ though? I see that it means $d| 3(a + b)$ but where does the gcd come in – Amad27 Dec 12 '16 at 7:20
• I see. Is it because $d|3a, d|3b$ $d$ must divide any factor of either $3a$ or $3b$ so it must divide their common factor – Amad27 Dec 12 '16 at 7:21
• Yes, sorry that now only I could see your comment. You are right. – user371838 Dec 12 '16 at 7:22

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$.

• How do I use the $\gcd(a, b) = 1$ though? – Amad27 Dec 12 '16 at 7:10
• If there is a $r>1$ so that $r \mid b, r \mid \gcd (2a+b,a+2b) \mid a+2b$ then $r \mid a$, a contradiction. Thus, $\gcd (2a+b,a+2b) \mid 3$. – Tengu Dec 12 '16 at 7:12