Prove $\,17\mid 2a+3b \,\Rightarrow\, 17\mid 9a + 5b$

Question

So, according to the book, for all $a, b, c$ that are elements of integers, it holds that $a|b$ implies $a|bx$ for all $x$ that is an element of integers. In other words it works for all ARBITRARY $x$ in the universe $Z$.

However, please consider this question:

When $2a + 3b$ is a multiple of $17$, prove that $17$ divides $9a + 5b$.

Proof(textbook):

We observe that $17|(2a + 3b) \implies 17|(-4)(2a + 3b)$ by the theorem where $a|b$ implies $a|bx$ for all $x$ that is an element of integers. Also since $17|17$ it follows that $17|[(17a + 17b) + (-4)(2a + 3b)]$ and consequently this simplifies to $17|(9a + 5b)$.

My problem with proof:

The book chooses the $x = -4$ for the arbitrary $x$ that is part of the universe $Z$, but I find that this isn't arbitrary at all because I'm pretty sure that if I used any other number for $x$ in the universe of $Z$ it wouldn't work with the proof. It would then seem that the book specifically chose it as $-4$ because the part where they include $17|17$ seems to be specific towards $-4$ being $x$ as well. Am I right in this? How would I solve questions like these?

Answer 1

The proof given is an instance of a magic proof. It works quite nicely, but gives little indication of how one reaches it.

Let us compare $2a+3b$ and $9a+5b$. Can we multiply the $2$ by something to get a result which is congruent to $9$ modulo $17$? Yes, multiplying by $13$ will do it. Let us see what this does to the whole expression $2a+3b$.

We get $$13(2a+3b)=26a+39b\equiv 9a+5b\pmod{17}.$$ Since $17$ divides $2a+3b$, it divides $13(2a+3b)$. But since this is congruent to $9a+5b$ modulo $17$, it follows that $9a+5b$ is divisible by $17$.

Note that $-4\equiv 13\pmod{17}$, so, modulo $17$, multiplying by $-4$ has the same effect as multiplying by $13$.

Now we can if we wish hide our preliminary work, and just say multiply by $13$, or, more mysteriously still, by $-4$.

Answer 2

HINT:

Eliminate one unknown $$9(2a+3b)-2(9a+5b)=?$$

Answer 3

$\smash[b]{{\rm mod}\ 17\!:\,\ 0\equiv 2a\!+\!3b\iff 0\equiv \dfrac{9}2(\color{#0a0}{2a}\!+\!3b)\equiv \color{#0a0}{9a}\!+\!\overbrace{(\color{#c00}{-4})3}^{\large \equiv\,5}\,b\,\ }$ by $\ \dfrac{9}2\equiv \dfrac{-8}2\equiv \color{#c00}{-4}_\phantom{I_{I_{I_{I_{I_I}}}}}$

Generally equations are preserved by scalings by invertible numbers. We chose the scale factor $\,9/2\,$ so to get the sought coeff of $\,a,\ $ i.e. to change $\,\color{#0a0}{2a}\,$ into $\,\color{#0a0}{9a}\,$ we scale by $\,9/2\equiv \color{#c00}{-4}$

Remark $\ $ More geometrically, if we change notation $\,a,b \to y,x\,$ and view the equations as lines, then we see they are equivalent because they are same slope lines through the origin:

$\quad \begin{array}{l} 2y+3x\equiv\, 0\iff y\,\equiv\, -\frac{3}2x\\ 9y+5x\equiv\, 0\iff y\,\equiv\, -\frac{5}9x\end{array}\ \ $ have equal slopes $ \, -\dfrac{3}2\equiv -\dfrac{5}9\ $ by $ \ 3\cdot 9\equiv 2\cdot 5\,\pmod{\!17}$