Writing direct proofs Let $x$, $y$ be elements of $\mathbb{Z}$. Prove if $17\mid(2x+3y)$ then $17\mid(9x+5y)$.  Can someone give advice as to what method of proof should I use for this implication? Or simply what steps to take?
 A: So $\,\exists\;k\in\Bbb Z\,\;\;s.t.\;\;\;2x+3y=17k\,$:
$$9x+5y=17x-8x+17y-12y=17(x+y)-4(2x+3y)=17\left(x+y-4k\right)\Longrightarrow$$
$$\Longrightarrow17\mid (9x+5y)$$
A: I would write the equations in $\mathbb{Z}_{17}$, which is a field, because $17$ is prime, so linear algebra applies:
$$ 2x+3y=0 $$
is a linear equation of two variables, and you seek to prove that it implies
$$ 9x+5y=0 $$
which means they're linearly dependent. Two equations are linearly dependent if and only if one is a multiple of the other - and this should be easy to prove.
Edit: Since you asked about proof strategy, I'd like to emphasize that this is not some random trick; the condition $p|x$ is not very nice to work with algebraically, but because $\mathbb{Z}_p$ is a field, the equivalent statement $x\equiv 0\mod p$ (I omitted the $\mod 17$ and the $\equiv$ above to make it look more like familiar algebra) is much simpler and better, because you can multiply, add and create linear spaces over $\mathbb{Z}_p$ that behave (in many ways) like real numbers.
A: Given $17 | 2x + 3y$ then $17 | (17x + 17y) - 4(2x + 3y)$ which says $17|9x + 5y$.
A: $\rm\begin{eqnarray}{\bf Hint}\ \ \  a\ (cx\!+\!dy)\!\!\!\!\!\!&\ - &\rm\! c\ (ax\!+\!by)\ \ =\ \ (ad\!-\!bc)y \\
\rm thus\ \ \ \  p\mid cx\!+\!dy \!\!\!\!&\iff&\rm\!\!\! p\mid ax\!+\!by\ \ if\ \ p\mid ad\!-\!bc,\,\ p\nmid a,c,\,\ p\ prime \end{eqnarray}$
