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.

I am reading this book. In the example 1.1 they said to prove this problem.

probelm

Let $x$ and $y$ be integers. Prove that $2x + 3y$ is divisible by $17$ iff $9x + 5y$ is divisible by $17$

the solution they provided is

$$17 \mid (2x + 3y) \implies 17 \mid [13(2x + 3y)]$$ or $$17 \mid (26x + 39y) \implies 17 \mid (9x + 5y)$$ and conversely,

$$17 \mid (9x + 5y) \implies 17 \mid [4(9x + 5y)]$$ or $$ 17 \mid (36x + 20y) \implies 17 \mid (2x + 3y)$$

I can't understand how the concluded this

$$17 \mid (26x + 39y) \implies 17 \mid (9x + 5y)$$ implication and this

$$17 \mid (36x + 20y) \implies 17 \mid (2x + 3y)$$

the only rule I know is

if $\;a|b\;$ then $\;a|bk$.

where a,b and k are integers. we can't deduce the above two implication (that is I confused) using this rule isn't it? is there any other point to determine that above two implications are true?

share|improve this question
1  
Split the 26x into 17x + 9x. Do the same for 39y = 34y+ 5y. –  Scott H. Apr 20 '13 at 5:18
1  
This site has latex support, and looks like you are aware of it. Please do not use the code formatting for math. If you want to center the math formulae, you can use $$. I have edited your answer as an example. –  Aryabhata Apr 20 '13 at 5:21
1  
@Aryabhata: yes. I am novice here. I couldn't cope with right arrow. I will try my best to use latex in next time. sorry for that. –  lakshman Apr 20 '13 at 5:28
    
add comment

3 Answers

up vote 4 down vote accepted

Hints: $26x=9x+17x$, $39y=5y+17y+17y$

share|improve this answer
add comment

A useful strategy in such problems can be to eliminate one of the variables. So multiply $2x+3y$ by $5$, multiply $9x+5y$ by $3$, and subtract. We get $$5(2x+3y)-3(9x+5y)=-17x.$$ Now suppose that $17$ divides $2x+3y$. Since $17$ also divides $-17x$, it follows that $17$ divides $3(9x+5y)$. But $17$ is relatively prime to $3$, so $17$ divides $9x+5y$.

A very similar argument shows that if $17$ divides $9x+5y$, then $17$ divides $2x+3y$.

share|improve this answer
    
+1 for great argument...:) –  lakshman Apr 20 '13 at 5:53
add comment

You can also use the rules $$ a\mid b\quad\text{and}\quad a\mid c\quad\Rightarrow\quad a\mid(b+c)\quad\text{and}\quad a\mid(b-c) $$ which should be helpful here.

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.