# Basic number theory problem

• Jul 23rd 2012, 02:27 AM
susan12
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
• Jul 23rd 2012, 05:23 AM
emakarov
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).
• Jul 23rd 2012, 07:34 AM
richard1234
Re: Basic number theory problem
You can freely add/subtract multiples of 17. From $17 | (26x + 39y) \Rightarrow 17 | 9x + 5y$, the writer subtracted 17x + 34y, which is valid (because it is congruent to 0 (mod 17)).
• Jul 23rd 2012, 08:38 AM
Deveno
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.