<s>[INST] Let $a,b,c$ be integers such that
$\gcd(a,6)=3=\gcd(b,6)$. Show that $\gcd(a+b,6)=6$. Let $a,b,c$ be integers such that
$\gcd(a,6)=3=\gcd(b,6)$.
Show that $\gcd(a+b,6)=6$.
Attempt:
Let $d = \gcd(a+b,6)$.
Then, by definition, $d \mid (a+b)$ and $d \mid 6$. It means that $d=1,2,3$ or $6$. On the other hand, we have
$3\mid a$ and $3 \mid b$. Write
$a = 3m$ and $b=3n$ for some integers $m$ and $n$. Then, $a+b=3m+3n=3(m+n)$ and so
$3 \mid (a+b)$. But, $d \mid (a+b)$. Now, $a+b = dp$ for some integer $p$.
Thus, we have $3 \mid dp$ which means $3 \mid d$ or $3 \mid p$.
If $3 \mid d$, then $d=3k$ for some integer $k$. Hence, $d$ is either $3$ or $6$.
But, how to get $d=6$?
 [/INST] Since $\gcd(a,6)=\gcd(b,6)=3$, then $a=3m$ and $b=3n$ for some odd $m$ and $n$.
Thus, $a+b=3(m+n)$ while $m+n$ is even, so $6\mid a+b$.
</s>