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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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|cite|improve this question
Split the 26x into 17x + 9x. Do the same for 39y = 34y+ 5y. – Scott H. Apr 20 '13 at 5:18
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
@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
up vote 4 down vote accepted

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

share|cite|improve this answer

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|cite|improve this answer
+1 for great argument...:) – lakshman Apr 20 '13 at 5:53

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|cite|improve this answer

Your Answer


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.