# If $a\mid b$ then $\gcd(a,c) \leq \gcd(b,c)$

I need to show that:

If $a\mid b$ then $\gcd(a,c) \leq \gcd(b,c)$ where $a,b,c$ are positive integers.

I've come up with this, but I'm not 100% sure that it's correct:

Assume $a\mid b$, then $a \leq b$. Multiply both sides by an integer, $x$, such that $ax \leq bx$. Then add $cy$ for positive integer, $c$, and some integer, $y$, to both sides such that $ax + cy \leq bx + cy$. Then by EEA, $ax + cy = \gcd(a,c)$ and $bx + cy = \gcd(b,c)$. Therefore, $\gcd(a,c) \leq \gcd(b,c)$

• Be-careful $3 \mid -3$ but $3 > -3$ – alkabary Jun 14 '15 at 21:32
• Hint for the original question: If $d\mid a$ then $d\mid b$. – Thomas Andrews Jun 14 '15 at 21:32
• You can write $\gcd(b,c)=bx+cy$, but one among $x$ and $y$ is negative. – egreg Jun 14 '15 at 21:33
• @alkabary Is it reasonable to assume $a|b$ implies $a \leq b$ if both a and b are positive integers? – DayDreamerz Jun 14 '15 at 21:34
• yes @DayDreamerz, I just didn't see + integers – alkabary Jun 14 '15 at 21:34

This doesn’t work, I’m afraid. The extended Euclidean algorithm gives you some pair of integers $x$ and $y$ such that $ax+cy=\gcd(a,c)$, but there’s no guarantee that $bx+cy=\gcd(b,c)$ for that same pair of integers.

HINT: Since $a\mid b$, you know that for every $d$, if $d\mid a$, then $d\mid b$.

• Ah okay, how about, consider $\gcd(b,c) = bg + ck$ for some integers $g$ and $k$. If $d|a$ then $d|b$ by TD, and $d|c$ then $d | (bx + cy)$ for all integers $x,y$ by DIC. Then, let $x = g$ and $y = k$. Then $d | (bg + ck) = \gcd(b,c)$. Thus, $\gcd(a,c) = d \leq \gcd(b,c)$ – DayDreamerz Jun 14 '15 at 21:41
• @DayDreamerz: You can do it this way, but you’re making it far more complicated than is necessary. Just let $d=\gcd(a,c)$. Then $d\mid a$ and $d\mid c$, so $d\mid b$ and $d\mid c$, and therefore $d\mid\gcd(b,c)$. – Brian M. Scott Jun 14 '15 at 21:43
• Oh my gosh, that is much more simpler than the spaghetti I came up with. Thank you very much for your help! – DayDreamerz Jun 14 '15 at 21:45
• @DayDreamerz: You’re very welcome! – Brian M. Scott Jun 14 '15 at 21:45

Let $\,b = an.\,$ If $\,d\mid a,c\,$ then $\,d\mid an,c,\,$ so the set $S =$ common divisors of $\,a,c\,$ is a subset of $T =$ common divisors of $\,an,c,\$ so $\ S\subseteq T\Rightarrow \max S \le \max T,\$ i.e $\ (a,c)\le (an,c).$

Alternatively: $\,\ (a,c)\mid an,c\,\Rightarrow\,(a,c)\mid(an,c),\,$ therefore $\ (a,c)\le (an,c).$