1

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.

barak manos
  • 43,109
Belphegor
  • 1,268
  • 6
  • 27
  • 51
  • Well, presumably they use the particular statement later on for something. It seems that they're going to then notice that $$-8a + 17 a = 9a$$ –  Jul 05 '14 at 06:55
  • Is there a way to figure out how it was -4 another way. – Belphegor Jul 05 '14 at 07:00
  • What do you mean? Multiplying by $-4$ isn't the only way to proceed with the proof; it just happens to work out well because it gives a decent way to relate a statement about $2a$ to a statement about $9a$ using $17$. –  Jul 05 '14 at 07:02
  • See my answer for a method that works in all cases and does not require figuring out anything, since there is an efficient algorithm to find the inverse of any invertible element in Z/nZ. – user21820 Oct 20 '14 at 11:47

5 Answers5

2

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.

Adriano
  • 41,576
1

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.

harogaston
  • 113
1

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

user21820
  • 57,693
  • 9
  • 98
  • 256
0

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

Rebecca J. Stones
  • 26,845
0

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

barak manos
  • 43,109