General method for solving problems like $17 \mid 2x + 3y \Longleftrightarrow 17 \mid 9x + 5y$

Question

Note: This is not a duplicate of Understanding a proof that $17\mid (2x+3y)$ iff $17\mid(9x +5y)$ or Understanding a proof that $2x + 3y$ is divisible by $17$ iff $9x + 5y$ is divisible by $17$.

I was reading through Naoki Sato's notes on number theory. I am somewhat unsatisfied with the given solution to this problem:

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

Solution. $17 \mid 2x + 3y \Rightarrow 17 \mid 13(2x + 3y)$, or $17 \mid 26x + 39y \Rightarrow 17 \mid 9x + 5y$, and conversely, $17 \mid 9x + 5y \Rightarrow 17 \mid 4(9x + 5y)$, or $17 \mid 36x + 20y \Rightarrow 17 \mid 2x + 3y$.

I do understand the solution but it seems like an unmotivated approach. How would one get the numbers $13$ and $4$ except for clever guessing? Is there a general method for solving such problems? That is, some theorem that trivializes such problems. I don't know much about modular arithmetic but I've noticed that $13$ and $4$ are inverses modulo $17$, i.e. $17 \cdot 4 \equiv 1 \pmod{17}$. I believe it might have something to do with that.

Answer 1

Remember that if $17|2x+3y$, this is the same as saying $2x+3y\equiv 0\mod(17)$, and therefore $2x\equiv -3y\mod(17)$. Solving for $x$ requires the multiplicative inverse of $2\mod(17)$, which happens to be $9$. Therefore $x\equiv -(3\cdot9)y= -27y\equiv -10y\equiv 7y\mod(17)$

Now we do the same for the other divisibility statement: $17|9x+5y\Longrightarrow 9x\equiv -5\mod(17)$. We already know that $2$ and $9$ are multiplicative inverses $\mod(17)$, so this is equivalent to $x\equiv-10y\equiv 7y\mod(17)$.

Hang on, that's the same as what we got before! This means that assuming one of $2x+3y$ or $9x+5y$ to be divisible by $17$ leads to the other being divisible by it also, thus proving the claim.

Addendum: I got carried away with my method and forgot to answer the question you actually asked. $4$ and $13$ come from solving either $2m\equiv 9\mod(17)$ or $3n\equiv 5\mod(17)$. Solving the first requires the inverse of $2\mod(17)$, which we already know to be $9$; therefore $2m\equiv \frac{1}{2}\mod(17)\Longrightarrow m\equiv \frac{1}{4}\mod(17)$. The inverse of $4\mod(17)$ is $13$, so we conclude that $m\equiv 13\mod(17)$.

Now, solving for $n$ in $3n\equiv 5\mod(17)$ leads to $n\equiv\frac{1}{3}\cdot5\mod(17)$. The multiplicative inverse of $3\mod(17)$ is $6$, so we have $n\equiv6\cdot5=30\equiv 13\mod(17)$.

Thus $m=n$. What we have just done is found (and confirmed) the unique integer $k$ such that $k(2x+3y)\equiv 9x+5y\mod(17)$. This of course means that $2x+3y\equiv\frac{1}{k}(9x+5y)\mod(17)$, and if $13$ is substituted for $k$, we get $13(2x+3y)\equiv9x+5y\mod(17)$ and $2x+3y\equiv4(9x+5y)\mod(17)$. Since they are integer multiples of each other $\mod(17)$, assuming one to be an integer multiple of $17$ leads to the other being an integer multiple of $17$, i.e. they are both divisible by $17$.

In general: if you have $ax+by\equiv cx+dy\mod(p)$, where $p$ is a prime, then it is true that $p|ax+by$ and $p|cx+dy$ if and only if $a^{-1}c\equiv b^{-1}{d}\mod(p)$.

Answer 2

Let $(c,d)$ be an ordered pair in $((\mathbb{Z}/17\mathbb{Z})^*)^2$, and let $(x,y)$ is be any pair of integers s.t. $cx+dy$ is divisible by $17$. Then let $(c',d')$ be another pair in $((\mathbb{Z}/17\mathbb{Z})^*)^2$. Then $c'x+d'y$ is also divisible by $17$ iff either:

• There is an element $a \in (\mathbb{Z}/17 \mathbb{Z})^*$ such that $(ac,ad)=(c',d')$, or

• Both $x$ and $y$ are each divisible by $17$.

This is a straightforward exercise to check. Note that $17$ can be replaced by any prime $q$. Furthermore, this leads to a fast algorithm to check, as for any prime $q$, the equation $c=ac'$ can be solved for $a$ in time polylog$(q)$, and then it is straightforward to check whether the equation $d=ad'$ holds mod $q$.

Answer 3

I think a variation of Euclid's GCD algorithm can help out.

Line 1: $9x+5y=4(2x+3y)+x-7y$

Line 2: $2x+3y=2(x-7y)+17y$

Stop here since one of the coefficients of x or y is 0.

Suppose 17 divides $2x+3y$, then it must divide $(x-7y)$ by line 2. If it divides both, 17 must also divide $(9x+5y)$ by line 1.

Combine the lines to get $(9x+5y)=4[2(x-7y)+17y]+x-7y=9(x-7y)+4 \cdot 17y$

So if $17$ divides $9x+5y$, it also divides $(x-7y)$. But by line 2, If 17 divides $(x-7y)$ then it divides $(2x+3y)$.