3
$\begingroup$

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

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

1 Answer 1

Reset to default
4
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Ah, i see. $m$ and $n$ must be odd, otherwise, the $\gcd(a,6)$ and $\gcd(b,6)$ are $6$ right? $\endgroup$
    – lap lapan
    Dec 31, 2020 at 3:53
  • $\begingroup$ that's right, @user795084 $\endgroup$
    – J. W. Tanner
    Dec 31, 2020 at 3:54
  • $\begingroup$ nice correction. thanks $\endgroup$
    – lap lapan
    Dec 31, 2020 at 3:55
  • $\begingroup$ 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? $\endgroup$
    – lap lapan
    Dec 31, 2020 at 4:03
  • $\begingroup$ @user795084 Clearly $d \leq 6$. Since $6|a+b$ and $6|6, d = 6$. $\endgroup$
    – Derek Luna
    Dec 31, 2020 at 7:12

Not the answer you're looking for? Browse other questions tagged .