1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ $ab|btma \wedge ab|asnb \Rightarrow a|cd$ Is this correct? $\endgroup$
    – mod
    Jan 18 '16 at 18:39
  • $\begingroup$ @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. $\endgroup$
    – Arthur
    Jan 18 '16 at 18:41
  • $\begingroup$ I've got it. Thank you. $\endgroup$
    – mod
    Jan 18 '16 at 18:44
2
$\begingroup$

Hint $$ mac+bnc=cd$$

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

$\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.