## Basic number theory problem

Let x and y be integers. Prove that 2x + 3y is divisible
by 17 iﬀ 9x + 5y is divisible by 17.
Solution. 17 | (2x + 3y) ⇒ 17 | [13(2x + 3y)], or 17 | (26x + 39y) ⇒
17 | (9x + 5y), and conversely, 17 | (9x + 5y) ⇒ 17 | [4(9x + 5y)], or
17 | (36x + 20y) ⇒ 17 | (2x + 3y)

Could someone please help me understand this solution. I do not understand it at all. What basis do they have for doing such operations? The solution just doesn't make sense
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 Mentor Blog Entries: 8 Which part don't you understand?? The only two rules they used were $$n\vert m~\Rightarrow~n\vert mk$$ and $$n\vert m,~n\vert k~\Rightarrow~n\vert (m+k)$$
 Why do they multiply 2x+3y by 13? and why do they multiply 9x+5y by 4? why not some other numbers?

Recognitions:
Gold Member
Staff Emeritus

## Basic number theory problem

 Quote by Gravitational Why do they multiply 2x+3y by 13? and why do they multiply 9x+5y by 4? why not some other numbers?
So they can get the desired answer. If you use other numbers, you'll get other equivalent statements.

How did they know that would give the desired answer? Trial and error would work. Or, you could try and write down an equation that says "If I multiply by n, then the answer I get is the one I want".

 Quote by Gravitational Could someone please help me understand this solution. I do not understand it at all. What basis do they have for doing such operations? The solution just doesn't make sense
You're asking the wrong question, it seems. You don't seem to have meant "I don't understand this solution!" -- you seem to have meant "How could I have come up with this solution myself?"
 Mentor Blog Entries: 8 Do you know modulo arithmetic?

 Quote by micromass Do you know modulo arithmetic?
no, but i dont think modulo arithmetic is necessary in this problem
 I understand why they multiplied by 13, but i dont see the significance in multiplying by 4

Mentor
Blog Entries: 8
 Quote by Gravitational no, but i dont think modulo arithmetic is necessary in this problem
It's not necessary in understanding the solution. But it's necessary in understanding why they did what they did.

Blog Entries: 2
 Quote by Gravitational I understand why they multiplied by 13, but i dont see the significance in multiplying by 4
If you understand the first part, then you should understand the logic of the second part. Both parts are required to show the "if and only if" condition. Basically, they used multiplication by 4 since 4*9 = 17*2 plus 2 and that is the way to reduce the 9x to 2x mod 17. Because of the iff part, taking care of the x variable also takes care of the y variable.
 2x + 3y is divisible by 17, there is an integer k such that (2x + 3y)/17 = k <=> 2x + 3y = 17k. Multiply both sides by 13 13(2x + 3y) = 13 * 17k <=> 26x + 39y = 13 * 17k <=> 9x + 5y + (17x + 34y) = 13 * 17k <=> (moving over the thing in the parantheses to the right-hand side and factoring out 17 9x + 5y = 13 * 17k - (17x + 34y) = 13 * 17k - 17(x + 2y) = 17(13k - (x + 2y)) Thus 9x + 5y is divisible by 17. I actually think this proof is better

 Quote by Gravitational 2x + 3y is divisible by 17, there is an integer k such that (2x + 3y)/17 = k <=> 2x + 3y = 17k. Multiply both sides by 13 13(2x + 3y) = 13 * 17k <=> 26x + 39y = 13 * 17k <=> 9x + 5y + (17x + 34y) = 13 * 17k <=> (moving over the thing in the parantheses to the right-hand side and factoring out 17 9x + 5y = 13 * 17k - (17x + 34y) = 13 * 17k - 17(x + 2y) = 17(13k - (x + 2y)) Thus 9x + 5y is divisible by 17. I actually think this proof is better
solution*

Blog Entries: 2
 Quote by Gravitational 2x + 3y is divisible by 17, there is an integer k such that (2x + 3y)/17 = k <=> 2x + 3y = 17k. Multiply both sides by 13 13(2x + 3y) = 13 * 17k <=> 26x + 39y = 13 * 17k <=> 9x + 5y + (17x + 34y) = 13 * 17k <=> (moving over the thing in the parantheses to the right-hand side and factoring out 17 9x + 5y = 13 * 17k - (17x + 34y) = 13 * 17k - 17(x + 2y) = 17(13k - (x + 2y)) Thus 9x + 5y is divisible by 17. I actually think this proof is better
More powerful if you use the Mod operations. In Mod 17, multiples of 17 == 0.

2x + 3y == 0 Mod 17
26x + 39y == 13* 0 Mod 17
9x + x*0 + 5y + y*0 == 13*0 Mod 17
9x + 5y == 0 Mod 17

I other words 9x+ 5y is divisible by 17 if 2x + 3y is divisible by 17

 Tags divisibility, mathematics, maths, number theory

 Similar discussions for: Basic number theory problem Thread Forum Replies Calculus & Beyond Homework 0 Calculus & Beyond Homework 2 Linear & Abstract Algebra 22 Linear & Abstract Algebra 12 Calculus & Beyond Homework 4