1
$\begingroup$

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?

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ – Amad27 Dec 12 '16 at 7:20
  • $\begingroup$ 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 $\endgroup$ – Amad27 Dec 12 '16 at 7:21
  • $\begingroup$ Yes, sorry that now only I could see your comment. You are right. $\endgroup$ – user371838 Dec 12 '16 at 7:22
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How do I use the $\gcd(a, b) = 1$ though? $\endgroup$ – Amad27 Dec 12 '16 at 7:10
  • $\begingroup$ 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$. $\endgroup$ – Tengu Dec 12 '16 at 7:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.