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

Savvycom software

Re: Basic number theory problem

Quote:

Originally Posted by

**susan12** Solution. 17 | (2x + 3y) ⇒ 17 | [13(2x + 3y)], or 17 | (26x + 39y) ⇒ 17 | (9x + 5y)

Perhaps the unclear step is 17 | (26x + 39y) ⇒ 17 | (9x + 5y). The reason is that 26x = 17x + 9x and 39y = 2 * 17y + 5y. So, if 26x + 39y = 17k for an integer k, then 9x + 5y + 17(x + 2y) = 17k and thus 9x + 5y = 17(k - x - 2y).

Re: Basic number theory problem

You can freely add/subtract multiples of 17. From $\displaystyle 17 | (26x + 39y) \Rightarrow 17 | 9x + 5y$, the writer subtracted 17x + 34y, which is valid (because it is congruent to 0 (mod 17)).

Re: Basic number theory problem

for emphasis:

suppose p (a positive integer) divides a+b and p divides a. then p must also divide b.

p divides a+b means a+b = kp, for some integer k.

p divides a means a = mp, for some integer m.

so then b = (a+b) - a = kp - mp = (k - m)p, and surely k - m is an integer if k and m are, so p divides b.