# Congruences and proving

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

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.

-
How did you get $7a+2b\equiv 14a+4b$? –  Alex Becker Apr 30 '12 at 17:15
If $k|n$ then k must also divide mn for any integer n, right? Or I missed something? –  Straightfw Apr 30 '12 at 17:19
But that assumes what you were trying to prove, that $7a+2b$ is divisible by $17$. @Straightfw –  Thomas Andrews Apr 30 '12 at 17:20
Take $a=b=1$; is $7\cdot1+2\cdot1\equiv 14\cdot1+4\cdot1\pmod{17}$? –  Brian M. Scott Apr 30 '12 at 17:20
Much better; now you've got it. –  Brian M. Scott Apr 30 '12 at 17:29

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

-
Wow, that's a nice solution, sir! Thank you very much :) –  Straightfw Apr 30 '12 at 17:35
@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$ –  Thomas Andrews Apr 30 '12 at 17:47
I know but it just went much slicker in your answer :) –  Straightfw Apr 30 '12 at 17:49

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.

-
I have not the slightest idea what you're talking about, good sir, but thank you very much! –  Straightfw Apr 30 '12 at 18:07
@Straightfw Are you not familar with lines and their slopes? –  Bill Dubuque Apr 30 '12 at 18:10
I'm a newbie so using lines to solve a problem with congruences seems like a pure magic to me. –  Straightfw Apr 30 '12 at 18:11
@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. –  Bill Dubuque Apr 30 '12 at 18:28

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)$$. - The previous solution was wrong either way ;) – Straightfw Apr 30 '12 at 18:07 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}\$.

-