# Prove: If $a|c \wedge b | c \wedge (a, b) = d \Rightarrow ab | cd$

I know that $(a,b)=d \Rightarrow ma+bn=d, (m,n\in Z)$.

$ma+bn=d/*c \Rightarrow cma+cnb=cd$

And I'm kinda stuck here. Any help or hint is appreciated.

You're very close. Note that $a\mid c$ and $b \mid c$, so you can do two substitutions: $c \mapsto as$ and $c \mapsto bt$ for some integers $s, t$. Now the last line you have reads $$btma + asnb = cd$$ Can you finish?

• $ab|btma \wedge ab|asnb \Rightarrow a|cd$ Is this correct?
– mod
Jan 18 '16 at 18:39
• @optimistic_mathematician I was thinking more along the lines of "$btma + asnb = ab(tm + sn)$, which is obviously divisible by $ab$", but it amounts to exactly the same thing, yes. Jan 18 '16 at 18:41
• I've got it. Thank you.
– mod
Jan 18 '16 at 18:44

Hint $$mac+bnc=cd$$

Now show that $ab|mac$ and $ab|bnc$.