discrete mathematics and proofs Let $a$ and $b$ be in the universe of all integers, so that $2a + 3b$ is a multiple of $17$.
Prove that $17$ divides $9a + 5b$. 
In my textbook they do $17|(2a+3b) \implies 17|(-4)(2a+3b)$.
They do this with the theorem of $a|b \implies a|bx$.
However, I don't know how the book got $x=-4$.
What is the math behind this?
This is just a section of the steps that complete the proof.
Once I know how the book figured out $x$ was $-4$ then i will be happy.
 A: We seek integers $x,y,z$ such that:
$$
9a + 5b = x(2a + 3b) + 17(ya + zb)
$$
Comparing coefficients, we obtain:
$$
\begin{cases}
9 = 2x + 17y \\
5 = 3x + 17z
\end{cases}
\implies
\begin{cases}
~~~27 = 6x + 51y \\
-10 = -6x + -34z
\end{cases}
\implies
17 = 51y - 34z
\implies 1 = 3y - 2z
$$
Since $2$ and $3$ are coprime, this linear Diophantine equation has infinitely many solutions. By inspection, we see that one solution is $y = z = 1$. Substituting these values into either of the two original equations yields $x = -4$, as desired.

Since this solution isn't unique though, suppose that we instead took $y = 3$ and $z = 4$ so that $x = -21$. Then observe that since $17 \mid (17)(3a + 4z)$ and since $17 \mid (-21)(2a + 3b)$, it follows that $17 \mid ((17)(3a + 4z) + (-21)(2a + 3b))$ so that $17 \mid 9a + 5b$, as desired.
A: The proof goes like this:
It's clear that 17|17(a + b) = 17a + 17b for any a,b integers.
Let's see that 17|-8a -12b = (-4)(2a + 3b), well by hypotheses we know that 17|2a + 3b, so that also holds true. Here we are using that if n|x, then n|ax for all a integer.
Finally using the theorem that if n|x and n|y then n|(ax + by) for all a,b integers.
We have that 17|(-8a -12b) + (17a + 17b) = 9a + 5b which is exactly what we wanted to prove.
Using -4 is just a clever (not trivial) way to get to the final identity.
A: A completely different way is:
For any integers $a,b$ such that $2a + 3b ≡ 0 \pmod{17}$:
  $a ≡ 2^{-1}(-3b) ≡ 9(-3b) ≡ 7b \pmod{17}$
  $9a+5b ≡ 9(7b)+5b ≡ 68b ≡ 0 \pmod{17}$
A: The author of the book "cheated" here.
We know: if $17$ divides $2a+3b$, then $17$ divides $k(2a+3b)$ for any integer $k$.
The author, aiming to write an interesting problem, would have chosen $k$ so that $(2k,3k) \text{ mod } 17$ didn't look like an obvious multiple of $(2,3)$ modulo $17$.  So the author of the question picked $-4$, so $(2k,3k) \text{ mod } 17=(9,5)$.  The author knew how to prove the claim, since the author chose $-4$.
When I first saw the problem (without knowing $-4$ in advance), it didn't strike me as obvious to multiply by $-4$.  As an attempt at a proof, I probably would have tried multiplying by $\{1,2,\ldots,16\}$ on a computer to see if any of them worked.  It would have found that $13$ works (which is $-4 \pmod {17}$).  Then I would have presented the proof without explaining the process of discovery (i.e., without mentioning the $15$ failed attempts).
A: *

*$9a+5b-x(2a+3b)=17a+17b$

*$(9-2x)a+(5-3x)b=17a+17b$

*$9-2x=17 \implies x=-4$

*$5-3x=17 \implies x=-4$
