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.

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