3
$\begingroup$

Prove that for $a,b \in Z$ such that $17\mid 2a+3b$, it is true that $17\mid 7a+2b$.

Could you please check my answer? Here it is:

For sure $17b\equiv 0 \pmod{17}$. Then Also $(2a+3b)\cdot5\equiv0\pmod {17}$. So $10a+15b-17b\equiv 0\pmod{17}$ so $2b\equiv 10a\pmod{17}$.

Hence $7a+2b\equiv 7a+10a\equiv 17a \equiv 0\pmod{17}$ q.e.d.

Is it OK? I don't feel confident in congruenced and would like to make sure if I haven't missed anything.

  • 2
    How did you get $7a+2b\equiv 14a+4b$?2012-04-30
  • 0
    If $k|n$ then k must also divide mn for any integer n, right? Or I missed something?2012-04-30
  • 2
    But that assumes what you were trying to prove, that $7a+2b$ is divisible by $17$. @Straightfw2012-04-30
  • 0
    Take $a=b=1$; is $7\cdot1+2\cdot1\equiv 14\cdot1+4\cdot1\pmod{17}$?2012-04-30
  • 0
    Oh.. yes, I see. I'll work on it and respond in a second :)2012-04-30
  • 0
    Changed! Is it OK now?2012-04-30
  • 1
    **Much** better; now you've got it.2012-04-30

4 Answers 4

4

Yes, that is a fine argument. A quicker trick might be to multiply by $12$:

$$0\equiv 12(2a+3b) = 24a + 36b = 7a + 2b + 17a + 34b \equiv 7a + 2b\pmod{17}$$

  • 0
    Wow, that's a nice solution, sir! Thank you very much :)2012-04-30
  • 0
    @Straightfw It's basically your solution, cleaned up. You can multiply $2a+3b$ by any value to get a similar result, you just need to find a value such that $2n\equiv 7\pmod {17}$. If you picked $n=13$, you'd get $0\equiv 26a+39b \equiv 9a+5b$2012-04-30
  • 0
    I know but it just went much slicker in your answer :)2012-04-30
2

Hint $\rm\ mod\ 17\!:\:$ lines $\rm\: Y\equiv -\dfrac{2}3\: X\:$ and $\rm\: Y \equiv -\dfrac{7}2\: X\ $ have equal slope by $\rm\: - 2\cdot 2\equiv - 7\cdot 3$

In fact $\rm\:mod\ 17\!:\ \dfrac{-2}3 \equiv \dfrac{15}{3}\equiv 5\equiv \dfrac{10}2\equiv \dfrac{-7}2,\:$ so both lines are the same as $\rm\: Y \equiv 5\:X,\:$ i.e.

$$\rm\:2\:X + 3\:Y \equiv 0\iff Y\equiv 5\:X\iff \:7\:X + 2\:Y \equiv 0\:$$

Hence we deduce that these equations all have the same solution sets $\rm (X,Y),\:$ i.e. the point $\rm\:(X,Y) = (a,b)\:$ lies on one line iff it lies on all of them. This answers you query (and more).

These equivalences depend crucially on the fact that the scaling maps employed were invertible, i.e. multiplying by $2$ and $3$ is invertible, by multiplying by $1/2\equiv 18/2\equiv 9,\:$ and $\rm 1/3 \equiv 18/3 \equiv 6.$

Generally, for any prime modulus $\rm\:p,\:$ nonzero elements are invertible (i.e. $\rm\mathbb Z/p$ is field). In this case the above may be viewed as saying that the usual normal forms for lines also work over fields. In particular, as above, two lines through $(0,0)$ are equal iff they have the same slope.

To be successful at modular arithmetic it is essential to learn to see precisely how it is (and is not) analogous to integer and rational arithmetic, so that one may successfully transfer well-honed intuition from these familiar arithmetic domains to less-familiar modular arithmetic domains. These key structural characteristics are brought to the fore when one studies abstract algebra. However, it is advantageous to begin recognizing such analogies as soon as possible, esp. when, as above, they are simple direct analogies of well-known elementary arithmetical methods.

  • 0
    I have not the slightest idea what you're talking about, good sir, but thank you very much!2012-04-30
  • 0
    @Straightfw Are you not familar with lines and their slopes?2012-04-30
  • 0
    I'm a newbie so using lines to solve a problem with congruences seems like a pure magic to me.2012-04-30
  • 0
    @Straightfw I've elaborated a little. It's worth your effort to try to comprehend this, even if at a later date when you have a bit more experience with modular arithmetic. In fact this method is algorithmic (mechanical), since it reduces the general problem to comparing line normal forms, whereas the *other* answers are magic, pulling the answer out of a hat.2012-04-30
  • 0
    Excellent approach. Never thought of using such an approach for these problems. +1 for that2015-06-21
0

I guess your solution is wrong. But see here, you finded, $2a \equiv 14b(mod7)$. Then $ 2a + 3b \equiv 14b + 3b( mod 17) \equiv 17b(mod 17) \equiv 0 (mod17) $$.

  • 0
    The previous solution was wrong either way ;)2012-04-30
0

Suppose that $2a+3b\equiv 0\pmod{17}$. Then $2a-14b\equiv 0 \pmod {17}$. Then $a\equiv 7b\pmod{17}$. Then $7a+2b\equiv 49b+2b\equiv 51b\equiv 0\pmod{17}$.

If such large numbers are a problem, from $2a+3b\equiv 0\pmod{17}$ we conclude that $-15a+3b\equiv 0\pmod{17}$, and therefore $b\equiv 5a\pmod{17}$. Thus $7a+2b\equiv 7a+10a\equiv 0\pmod{17}$.