# Elementary Number Theory.. If a divides..

If $a \mid (2c+3d)$ and if $-a \mid (c+d)$ then show that $3a \mid 3c$.

The only progress I can say I've made is that the question is basically asking to show that $a \mid c$, because the $3$ is only a constant.

-

Hint $\$ Below are a few possible approaches.

$(1)\ \ \rm\ a\ |\ c\!+\!d,\,2c\!+\!3d\:\Rightarrow\:a\ |\ 3(c\!+\!d)\!-\!(2c\!+\!3d) = c\ \Rightarrow\ 3a\:|\:3c$

$\rm(2)\ \ mod\ a\!:\,\ d\equiv -c\,\$ so $\rm\,\ 2c\equiv -3d\equiv 3c\:\Rightarrow\:c\equiv 0\:\Rightarrow\:a\:|\:c\:\Rightarrow\:3a\:|\:3c$

$\rm(3)\ \ mod\ a\!: \ \ \left[\begin{array}{ccc} 2 & 3 \\ 1 & 1 \end{array}\right]\left[\begin{array}{c} \rm c \\ \rm d\end{array}\right]\, \equiv\, \left[\begin{array}{c}\rm 0 \\ \rm 0\end{array}\right]\ \ \Rightarrow\ \left[\begin{array}{c}\rm c \\ \rm d\end{array}\right]\, \equiv\, \left[\begin{array}{c}\rm 0 \\ \rm 0\end{array}\right]\$ since the matrix has det $= -1$ so is invertible

-

HINT: Since $a\mid 2c+3d$, there is an integer $m$ such that $2c+3d=am$. Since $-a\mid c+d$, there is an integer $n$ such that $c+d=-an$. You now have

\left\{\begin{align*}&2c+3d=am\\&c+d=-an\;.\end{align*}\right.

What happens if you multiply the second equation by $3$ and subtract the first equation?

-
you get 3c+3d-2c-3d=c Does this mean a divides c? So 3a divides 3c? – Pink Panda Sep 18 '12 at 21:04
@PinkPanda: On the lefthand side; now what do you get on the righthand side? Can you use that to show that $a\mid c$? – Brian M. Scott Sep 18 '12 at 21:05
I'm not sure what 3am+3an would tell me. Is that what you're referring to? – Pink Panda Sep 18 '12 at 21:08
@PinkPanda: That should be $-3am-3an$. Factor out the $a$: it’s $a(-3m-3n)$. Is $-3m-3n$ an integer? – Brian M. Scott Sep 18 '12 at 21:10