-1

I have a question about divisibility and and division algorithm:

if C = Ax + By, D|C and D|B then D|A? I thought yes, because C is a combination of A and B, and if D divides B and C, then it must divide A. This is true? If so, how can I justify (mathematically) Thanks.

Thais
  • 3

1 Answers1

2

Since $D$ divides $A,C$, we can write $A=mD$ and $C=nD$ for some $m,n$. But then $$ \begin{split} C&= Ax + By \\ nD&= mD + By \\ (n-m)D&= By \end{split} $$ But then notice that this just implies $D$ divides $By$, not necessarily $B$ or $y$. This suggests there is a counterexample. See if you can come up with one! [Maybe start 'backwards' by choosing $D$ to be a prime that divides $C$ and $B$ but perhaps not $A$.]

mathematics2x2life
  • 13,322