If $\gcd(a,b) = 1$, show that $\gcd(2a+b, a+2b)=1 \mbox{ or } 3$

3,866

Solution 1

Since $\gcd(a,b) = 1$, there exist integers $x,y$ such that $ax + by = 1.$

Let $d = \gcd(2a+b, a+2b).$

Then $d\,{\large{|}}(2a+b)$ and $d\,{\large{|}}(a + 2b)$, hence

$$d{\large{{\;|\,}}}\bigl(2(2a+b) - (a + 2b)\bigr) \implies d{\,|\,}3a$$

$$d{\large{{\;|\,}}}\bigl(2(a+2b) - (2a + b)\bigr) \implies d{\,|\,}3b$$

Then

$$d{\,|\,}3a \implies d{\,|\,}3ax$$ $$d{\,|\,}3b \implies d{\,|\,}3by$$

Hence

\begin{align*} &d\,{\large{|}}(3ax + 3by)\\[4pt] \implies\; &d\,{\large{|}}\bigl(3(ax + by)\bigr)\\[4pt] \implies\; &d{\,|\,}3\;\;\;\;\text{[since$\;ax + by = 1$]}\\[4pt] \implies\; & d = 1\;\,\text{or}\;\,d = 3\\[4pt] \end{align*}

Solution 2

Hint: $$\require{cancel} \gcd(2a+b,a+2b) \mid \gcd\big(2 \cdot(2a+\bcancel{b}) - (a+\bcancel{2b}), 2\cdot (\cancel{a}+2b)-(\cancel{2a}+b)\big)=\gcd(3a, 3b)$$

Share:
3,866

Related videos on Youtube

Guerlando OCs
Author by

Guerlando OCs

Updated on January 22, 2021

Comments

  • Guerlando OCs
    Guerlando OCs almost 3 years

    If $\gcd(a,b) = 1$, show that $\gcd(2a+b, a+2b)=1 \mbox{ or } 3$.

    What I tried:

    Suppose:

    $d \ | \ 2a+b$ and $d \ | \ a+2b$, then:

    $$2a+b = d\cdot k_1$$ $a+2b = d\cdot k_2$$

    therefore:

    $$3(a+b) = d(k_1+k_2)$$

    I also noted that if $\gcd(a,b)=1$ then $a+b$ has some interesting property for division but I cannot figure out exactly

  • Asim
    Asim over 2 years
    helpful answer, thanks