How Can You Prove the Divisibility of 2x + 3y and 9x + 5y by 17?

[futb0l]

I am reading Naoki Sato's notes on Number Theory:
http://donut.math.toronto.edu/~naoki/nt.pdf

I am on page 2, and doing Example 1.1...

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

There's ALREADY A SOLUTION on the book, but I do not understand it. I've read the theorems and also the other examples and found that I can understand them. I guess this one is different.

Can somebody please explain it to me clearer...??

Thanks.

 

[Muzza]

Assuming you know some basic things about congruences... If 2x + 3y is divisible by 17, then 2x + 3y == 0 (mod 17). Multiply both sides by 13 to get

13(2x + 3y) == 13(0) (mod 17)
<=>
26x + 39y == 0 (mod 17) ... (1)

But 26 == 9 (mod 17) and 39 == 5 (mod 17), så equation (1) is equivalent to

9x + 5y == 0 (mod 17).

Thus 9x + 5y is divisible by 17.

The other implication, that if 9x + 5y is divisible by 17 then 2x + 3y is divisible by 17, can be proved in a similar fashion.

*edit* After inspection of the PDF, I see that it doesn't use congruences at all. Right, if 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 and do some algebra magic (trying to be as clear as possible):

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.

 

[futb0l]

oh, great thanks..
you cleared it up beautifully...

i love this forum ;)