# If $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$

I came across this problem in my number theory text and am having a bit of trouble with it:

Prove if $c\mid ab$ and $\gcd(c,a)=d$, then $c\mid db$.

Here's what I have so far:

If $c\mid ab$, then there exists an integer $x$ such that $cx=ab$.
Because $\gcd(c,a)=d$, $d\mid c$ and $d\mid a$. Let $y$ be such that $dy=a$.
Then, $$cx=ab=dyb,$$ so $$cx \frac{d}{a} = db.$$ But I don't know how to show that $\frac{dx}{a}$ is an integer. Can anyone please offer ideas on what I've done so far?

Try using Bézout's identity. Since $\gcd(c, a) = d$, we know that there exist $s,t \in \mathbb Z$ such that: $$cs + at = d \iff bcs + abt = bd$$ Since $c \mid ab$, we know that there exists some $x \in \mathbb Z$ such that $cx = ab$, so: $$bd = bcs + (cx)t = c(\underbrace{bs + xt}_{\in ~ \mathbb Z})$$ Hence, $c \mid bd$, as desired.

Hint $\,\ c\mid cb,ab\,\Rightarrow\,c\mid (cb,ab)\overset{\rm\color{#c00}{ DL}}= (c,a)b = db\ \$ QED

Above we used the gcd Distributive Law ($\rm\color{#c00}{DL}$). Three proofs of DL are here.

Use the Bezout's theorem: There exists $x, y$ integers s.t. $cx + ay = d$. Then, multiplying by $b$ helds

$$c b x + a b y = b d$$

But $c \mid ab$, hence $c\mid bd$

There are no mistakes in what you've done so far, but I agree that it's not immediately apparent why $dx/a$ is an integer.

I would start by noting that the answer to this problem is well known when $d = 1$, so maybe I should try to turn it into a problem about relatively prime integers. So write $a = da'$ and $c = dc'$, and consider what the gcd of $a'$ and $c'$ is. Then see if you can carry on from there by reformulating the problem using $a'$ and $c'$ rather than $a$ and $c$.

Just a note: It is possible to do this problem without appealing to Bezout's Theorem. In other words, for those familiar with rings, the fact is valid in factorial rings, not just principal ones.