1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ You are right, the $-4$ was carefully chosen so that it would do the job. $\endgroup$ – André Nicolas Jul 24 '14 at 4:05
  • $\begingroup$ But how would I solve this then without this knowledge? Is it even possible? $\endgroup$ – Belphegor Jul 24 '14 at 4:17
  • $\begingroup$ There's a specific algorithm for calculating such things. (And a really really old one at that.) $\endgroup$ – Semiclassical Jul 24 '14 at 4:22
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Jul 24 '14 at 4:34
  • $\begingroup$ @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. $\endgroup$ – Dylan Stephano-Shachter Jul 24 '14 at 15:26
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Belphegor Jul 24 '14 at 5:43
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jul 24 '14 at 6:02
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Jul 24 '14 at 6:05
3
$\begingroup$

HINT:

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ See here for another example. $\endgroup$ – Bill Dubuque Oct 11 '19 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.