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