4

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?

alu
  • 349
  • This is hard to follow. – nonuser Jul 09 '20 at 21:03
  • How do you get gcd(a,qd)=1 from equation $(1)$. – hamam_Abdallah Jul 09 '20 at 21:07
  • @hamam_Abdallah We know, $\gcd(a,b)=1$. If $\gcd(a,qd)$ is not 1, then 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$ – alu Jul 09 '20 at 21:21
  • @Aqua Which part is hard to follow? – alu Jul 09 '20 at 21:22
  • I follow everything until the last line in which you write $\gcd(2a + b, a + 2b) = \gcd(qd, 2qd - 3).$ I suspect that the latter should be $\gcd(qd, 2qd - 3a),$ correct? – Dylan C. Beck Jul 09 '20 at 21:32
  • But this implies that $\gcd(2a + b, a + 2b) = \gcd(qd, -3) = 1$ or $3$ since $3$ is prime. – Dylan C. Beck Jul 09 '20 at 21:33
  • @Carlo You are correct, but $a$ was omitted because I already proved $\gcd(qd,a) = 1$, thus $\gcd(qd,2qd-3a) = \gcd(qd,2qd-3)$. Since $a$ and $qd$ have nothing in common, $a$ can be omitted and I focus on $qd$ and 3. Your second comment is correct. – alu Jul 09 '20 at 22:33
  • @Carlo I edited the proof after your comment – alu Jul 09 '20 at 22:35
  • "Since gcd(a,b)=1, from equation (1), we get gcd(a,qd)=1" How so? If we can do that in our heads we don't really need to do this proof in the first place. – fleablood Jul 09 '20 at 22:51
  • @fleablood I explained it in one comment. Alright, I'll add it to the proof. – alu Jul 09 '20 at 23:01
  • You are very generally making conclusions of which every single one of them is harder to verify and less intuitively obvious than the entire thing you are trying to prove in the first place. – fleablood Jul 09 '20 at 23:16
  • @fleablood "Every single one of them" - can you give me some examples? – alu Jul 09 '20 at 23:24
  • Sure, you claimed that because $2a+b=qd$ that therefore $\gcd(a,b) \implies \gcd(a,qd)=1$. Thats far from obvious. Then you claim that as $\gcd(2a+b, a+2b) = \gcd(qd, 2qd -3a)$ then $\gcd(2,3)=1\implies \gcd(qd,2qd-3a)=1,3$. Large leaps. – fleablood Jul 09 '20 at 23:37
  • @fleablood Thanks for the suggestions. I tried to remove the large leaps but seem to have found a flaw in the proof. I will try to solve it tomorrow. – alu Jul 10 '20 at 00:36
  • Why not do it the straight forward way? $2(2a+b) -(a+2b) =3a$ so $\gcd(2a+b,a+2b)|3a$. ANd $2(a+2b)-(2a+b) =3b$ so $\gcd(2a+b,a+2b)|3b$. If $p$ is a prime factor other than $3$ of $\gcd(2a+b,a+2b)$ then $p|a$ and $p|b$ but that contradicts $\gcd(a,b)=1$. And if $3^2|\gcd(2a+b,a+2b)$ then $3|a$ and $3|b$ which is a contradiction. So the only possible prime factor of $\gcd(2a+b,a+2b)$ is maybe but not nesc $3$ and if it is a prime factor it's only to the single power. – fleablood Jul 10 '20 at 01:33
  • @fleablood Thanks. I knew this proof already, though your proof has some new information. I was just trying something new, wondering if that would work. – alu Jul 10 '20 at 02:12

2 Answers2

2

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

AT1089
  • 973
  • I noticed it that 3|2a+b when 3 divides the difference between a and b. Thanks for writing it coherently. – alu Jul 10 '20 at 15:23
1

The OP's analysis seems valid to me. However, I don't think it is the intended answer. If $d$ is a common factor of both $2a + b$ and $a + 2b$, then it is a factor of their sum, which equals $3a + 3b = 3(a+b).$

Thus any common factor of $2a + b$ and $a + 2b$ will either be a factor of $3$ or a factor of $(a+b).$

user2661923
  • 35,619
  • 3
  • 17
  • 39