Problem 7

7. Show that the expressions $2x+3y$ and $9x+5y$ are divisible by $17$ for the same set of integral values of $x$ and $y$.

Proof: This is straightforward modular arithmetic. We have $2x+3y ≡ 0 \text{mod }17 ⇔ 13(2x+3y) = 26x+39y ≡ 9x+5y ≡ 0 \text{mod }17$, since $13$ is a unit in $ℤ/17ℤ$. Generally, when $z~\not |~a,b$, we have $ax+by$ is divisible by $z$ a prime for the same integral values as $cx+dy$ iff $-a^{-1}b ≡ -c^{-1}d \text{mod }z$, and when $z~|~a$ but $z~\not |~c$ then $(1,0)$ is a value for $ax+by$ but not for $cx+dy$, similarly for $z~|~c$ but $z~\not |~a$, and when $z~|~a,b$ we have the same values when $b$ and $d$ coincide in divisibility or lack of divisibility by $z$.