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.

  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Apr 2 '17 at 16:38
  • $\begingroup$ Hint: $ab = \gcd(a,b)\times lcm(a,b)$ $\endgroup$ – 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$.

  • $\begingroup$ 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$? $\endgroup$ – Daniel Vargas Apr 2 '17 at 20:15
  • 1
    $\begingroup$ @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 :) $\endgroup$ – Xam Apr 2 '17 at 21:01
  • $\begingroup$ @Daniel One can also avoid the GCD $\times$ LCM law by using the GCD Distributive Law - see my answer. $\endgroup$ – 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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.