How to prove $\gcd(a+m,b)=d$ when given $\gcd(a,b)=d$ and $b|m$?

Question

some say I shall use $a+m-m$..... But I do not get it.

Since $\operatorname{gcd}(a,b)=d$ then $a=q_1d$ and $b=q_2d$ And $b|m$ give $m= q_3b = q_3 q_2 d$

then $$a+m = q_1d+q_3q_2d = (q_1+q_3q_2)d$$

then $$\operatorname{gcd}(a+m,b) = \operatorname{gcd}((q_1+q_3 q_2)d, q_2 d)= d \operatorname{gcd}((q_1+q_3 q_2 ), q_2)$$

I must somehow prove that $\gcd((q_1+q_3 q_2 ), q_2)= 1$.... But here I need help.

Answer 1

Indeed, your proof goes well but you missed that $d$ not only divides $a$ and $b$, but it is also the greatest common divisor, meaning that $q_1$ and $q_2$ are relatively prime. Thus, we have $$\alpha q_1 + \beta q_2 = 1$$ for some integers $\alpha$ and $\beta$.

Then, $$\alpha q_1 + \beta q_2 = 1$$ $$\Rightarrow\alpha q_1 + \alpha q_3q_2-\alpha q_3q_2+ \beta q_2 = 1$$ $$\Rightarrow\alpha (q_1 + q_3q_2)+ (\beta-\alpha q_3) q_2 = 1$$ We quickly checked that $\alpha$ and $(\beta-\alpha q_3)$ are integers. Thus, we conclude that $(q_1 + q_3q_2)$ and $q_2$ are relatively prime, as desired.

Answer 2

Since $\operatorname{gcd}(a,b)=d$ then $a=q_1d$ and $b=q_2d$

You have one more condition about $q_1,q_2$.

Since $\gcd(a,b)=d$, then $a=q_1d,\ b=q_2d$ and $$\gcd(q_1,q_2)=1.$$ Can you take it from here?

Answer 3

First note that

1) $d | b$ since $\gcd(a, b) = d$,

2) $d | a+m$ since $d | b | m$ and $d | a$.

Now let $d'$ such that $d' | b$ and $d' | a + m$ and let us show that $d | d'$. Since $\gcd(a, b) = d$ it suffices to show that $d' | a$ (and $d' | b$). This is indeed the case since $d' | b | m$ and $d' | a + m$ imply $d' | a + m - m$.