$a\mid b,c\mid d\Rightarrow\,\gcd(a,c)\mid \gcd(b,d)$

Question

So far I have that $a|b$ implies $b=ax$ for some x in the integers and $c|d$ implies that $d=cy$ for some y in the integers. From here I can see that $gcd(a,c)|gcd(b,d)$ is logically equivalent to $gcd(a,c)|gcd(ax,cy)$ but I am not sure where to go from there.

Answer 1

If $a\mid b$ and $c\mid d$, then, since $\gcd(a,c)\mid a$ and $a\mid b$, $\gcd(a,c)\mid b$. For the same reason, $\gcd(a,c)\mid d$. So, since $\gcd(a,c)$ divides both $b$ and $d$, it divides $\gcd(b,d)$.

Answer 2

By gcd Universal Property $\ x\mid y,z\iff x\mid (y,z)\, \ $ [where $\,(y,z):=\gcd(y,z)$], $ $ so

$$\begin{align} a\mid b \,\Rightarrow\, \color{#0a0}{(a,c)}\mid a\mid \color{#c00}b\\ c\mid d \,\Rightarrow\, \color{#0a0}{(a,c)}\mid c\mid\color{#c00} d\end{align}\,\Rightarrow\, \color{#0a0}{(a,c)}\mid (\color{#c00}{b,d})\qquad\!\!$$

---

Or more generally notice $\ \begin{align} a\mid b&\,\Rightarrow\, b = a\bar a\\ c\mid d&\,\Rightarrow\, d = c\bar c\end{align}\ \ $ so it follows by below.

Lemma $\,\ \color{#c00}{(a,c)}(\bar a,\bar c)\,\mid\, (\color{#c00}a\bar a, \color{#c00}c\bar c)$

Proof $\ \ \ \ \ (a,c)(\bar a,\bar c) = (a\bar a,c\bar c,a\bar c,c\bar a )\mid a\bar a,c\bar c\,$ so it $\mid\, (a\bar a,c\bar c)\,$ by above universal property.

---

Or we can use $\,(w,x,y,z) = ((w,x),(y,z))\mid (w,x)\,$ by the gcd associative law.

The proof uses "gcd polynomial arithmetic" (associate, commutative, distributive) to expand the product, i.e. a gcd analog of $(a\!+\!c)(\bar a\!+\!\bar c) = a\bar a\! +\! c\bar c\! +\! a\bar c\! +\! c\bar a,\,$ as explained in the prior link.