# Show that if $\gcd(a,c)=d$, $a\mid b$ and $c\mid b$, then $ac\mid bd$

I'm trying to prove: if $\gcd(a,c)=d$, $a\mid b$ and $c\mid b$, then $ac\mid bd$.

I know that $d\mid b$ by transitivity of $d\mid a$ and $a\mid b$, $d\mid c$ and $c\mid b$, but I don't know how to advance from here.

• Your title and your body disagree (one says $c\mid b$ the other says $b\mid c$) and I think both are wrong and you mean $c\mid d$. – Thomas Andrews Apr 2 '17 at 16:38
• Hint: $ab = \gcd(a,b)\times lcm(a,b)$ – rogerl Apr 2 '17 at 16:55

I propose two solutions.

First solution: We use the hint given by rogerl in the comments. Since $a\mid b$ and $c\mid b$, then by the universal definition of $\text{lcm}$ we have that $\text{lcm}(a,c)\mid b$, then $\text{lcm}(a,c)\gcd(a,c)\mid b\gcd(a,c)=bd$. Now, as $ac=\text{lcm}(a,c)\gcd(a,c)$, thus $ac\mid bd$.

Second solution: In this proof we won't use the identity $ab=\gcd(a,b)\text{lcm}(a,b)$. Since $a\mid b$ and $c\mid b$, then there are $x,y$ such that $b=ax$ and $b=cy$. On the other hand, as $d=\gcd(a,c)$, then $a=a'd$ and $c=c'd$, with $\gcd(a',c')=1$. Now, we have $ax=cy$, which can be written in the form $$a'dx=c'dy \implies a'x=c'y.$$

Therefore, $c'\mid a'x$ and since $\gcd(a',c')=1$ we deduce that $c'\mid x$ (see here for a proof of this theorem), thus $c'd\mid xd$, i.e., $c\mid xd$, then we can set $xd=cz$, and hence $$bd=axd=a(xd)=acz=(ac)z.$$

So we conclude that $ac\mid bd$.

• Thanks, @Xam. I prefer the second solution rathen than the first one. There's only a question, How do you know that $gcd(a,'c')=1$? – Daniel Vargas Apr 2 '17 at 20:15
• @DanielVargas that's a property. If $d=\gcd(x,y)$ then $\gcd(x/d,y/d)=1$. I let you the pleasure of prove it :) – Xam Apr 2 '17 at 21:01
• @Daniel One can also avoid the GCD $\times$ LCM law by using the GCD Distributive Law - see my answer. – Bill Dubuque Apr 3 '17 at 0:03

$a,c\mid b\,\Rightarrow\,ac\mid ba,bc\,\Rightarrow\,ac\mid(ba,bc) = b(a,c)=bd$

Using prime factorization:

$$\gcd(a,c) = d ,~~ a|b ,~~ c|b \implies ac|bd$$

$$\gcd(\Pi p_k^{a_k}, \Pi p_k^{c_k}) = \Pi p_k^{d_k} ,~~ \Pi p_k^{a_k}|\Pi p_k^{b_k} ,~~ \Pi p_k^{c_k}|\Pi p_k^{b_k} \implies \Pi p_k^{a_k} \Pi p_k^{c_k} | \Pi p_k^{b_k} \Pi p_k^{d_k}$$

$$\forall k ~:~\max(a_k, c_k) = d_k ,~~ a_k \le b_k ,~~ c_k \le b_k \implies a_k + c_k \le b_k + d_k$$

which can be establishabled from $a_k + c_k \le 2d_k \le b_k + d_k$.

First, $gcd(a,c)=d \implies a=d·a' \wedge c=d·c'$ with $gcd(a',c')=1$

Moreover, $a|b \implies b=a·b'=d·a'·b' \wedge c|b \implies b=c·b''=d·c'·b''$

And then $d|b \implies b= d·\delta$

Now we only have to compute the product of $a$ and $c$ and $b$ and $d$.

$$a·c=d·a'·d·c' = d^2·a'·c'\wedge b·d= d·\delta·d = d^2·\delta \implies a'·c'=\delta$$

Note that $a' | \delta \wedge c' | \delta$ and $gcd(a',c')=1$, then, by the fundamental theorem of arithmetic we can see that we haven't common factors and for this reason: $$a' | \delta \implies c' | \frac{\delta}{a'} \implies b·d = a·c·\frac{\delta}{a'·c'} \implies ac| bd$$