Number Theory – Proof that $2x + 3y$ is Divisible by $17$ iff $9x + 5y$ is Divisible by $17$

divisibilityelementary-number-theorynumber theoryproof-explanation

I'm having some trouble understanding a proof on Naoki Sato's notes on Number Theory and I was wondering if you guys could give me some help. The problem is that I don't understand the last implication on the proof for example 1.1

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

Solution. 17 | (2x + 3y) ⇒ 17 | [13(2x + 3y)], or 17 | (26x + 39y) ⇒ 17 | (9x + 5y)
conversely, 17 | (9x + 5y) ⇒ 17 | [4(9x + 5y)], or 17 | (36x + 20y) ⇒ 17 | (2x + 3y).

My problem is that I don't understand how does 17 | (26x + 39y) imply 17 | (9x + 5y). If you could elaborate on this step I would be most grateful.

I'm sorry if this is an obvious question but I am a beginner and I just can't get it.

Thanks for your help in advance.

Best Answer

If $17\mid (26x+39y)$, and $17\mid (-17x-34y)$, then we may add to get $17\mid 9x+5y$. In general the rule is, if $p\mid a$ and $p\mid b$, then $p\mid (a+b)$.

Related Question