2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.