Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
2  
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
1  
Much better; now you've got it. –  Brian M. Scott Apr 30 '12 at 17:29
show 3 more comments

4 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
The previous solution was wrong either way ;) –  Straightfw Apr 30 '12 at 18:07
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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