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

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$.

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?

• You are right, the $-4$ was carefully chosen so that it would do the job. – André Nicolas Jul 24 '14 at 4:05
• But how would I solve this then without this knowledge? Is it even possible? – Belphegor Jul 24 '14 at 4:17
• There's a specific algorithm for calculating such things. (And a really really old one at that.) – Semiclassical Jul 24 '14 at 4:22
• The process of 'turning" the $2$ into $9$, modulo $17$ is a standard process in modular arithmetic. As for how to approach the problem yourself, I think the approach mentioned in the answer by lab bhattacharjee is more basic. But it gives a different proof, one that does not involve the $-4$. – André Nicolas Jul 24 '14 at 4:34
• @user3718584 In regards to your comment, be sure to remember that if you already knew to use -4, you wouldn't really be solving anything. – Dylan Stephano-Shachter Jul 24 '14 at 15:26

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$.

• What is this process for turning 2 into 9 exactly called? I searched up modular arithmetic and couldn't find anything about turning one numebr into another. – Belphegor Jul 24 '14 at 5:43
• Ordinarily, it is thought of as a two step process: turn the $2$ into a $1$ by multiplying $2$ by its modular inverse (that is a key term to search) and then turn the $1$ into $9$ by multiplying by $9$. The modular inverse of $2$ is $9$, since $2\cdot 9=18$. Multiply by $9$ again, to get $81$, which is congruent to $13$. For primes $p$ uite a bit bigger than $17$, modular inverses are found by using the extended Euclidean algorithm. – André Nicolas Jul 24 '14 at 6:02
• Bu for our numbers $9$ and $2$, you can think of it as dividing $9$ by $2$ modulo $17$. Of course you can't divide $9$ by $2$, but $9$ is congruent to $9+17$, which you can divide by $2$. – André Nicolas Jul 24 '14 at 6:05

HINT:

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

$$\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}$$

• See here for another example. – Bill Dubuque Oct 11 '19 at 15:22