# Let $a,b,c$ be integers such that $\gcd(a,6)=3=\gcd(b,6)$. Show that $\gcd(a+b,6)=6$. [duplicate]

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

• Since $d \mid 6$, then $6=dp$ i.e. $6q=dpq$ and then $6 \mid dpq$ i.e. $6 \mid d$. Is it true? Dec 31, 2020 at 3:30
• If true, then $6\mid d$ and $d \mid 6$ and hence $d=6$. Dec 31, 2020 at 3:32
• Same as in the linked dupe. Similarly, generally $\,(a,2n)=n=(b,2n)\Rightarrow (a+b,2n) = 2n\ \$ Dec 31, 2020 at 18:22

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$$.
• Ah, i see. $m$ and $n$ must be odd, otherwise, the $\gcd(a,6)$ and $\gcd(b,6)$ are $6$ right? Dec 31, 2020 at 3:53
• Since $6 \mid (a+b)$ and $d \mid (a+b)$, then $a+b = 6p$ and $a+b = dq$ for some integers $p$ and $q$. Hence, $6 \mid dq$ i.e. $6\mid d$ or $6 \mid q$. Since $d \mid 6$, then $d=6$ and we are done. Is it true? Dec 31, 2020 at 4:03
• @user795084 Clearly $d \leq 6$. Since $6|a+b$ and $6|6, d = 6$. Dec 31, 2020 at 7:12