If $23|3x+5y$ for some $x,y\in \mathbb{Z}$, then $23|5x-7y$?

Let $x,y$ be some integers such that $23|3x+5y$. Show that $23|5x-7y$ as well.

This was my exam question and I did not solve it. Could anyone give some insight how to do this? Even after the exam I can not solve it...

Hint $\bmod 23\!:\ \color{#c00}3x+\color{#0a0}5y\equiv \color{#c00}{-20}x+\color{#0a0}{28}y = -4(5x-7y)$

Remark $\ $ Generally scaling by a unit $\,u\,$ preserves equations, i.e. $\, ax+by\equiv 0\,\Rightarrow \ uax+uby\equiv 0,\,$ and conversely by scaling by $\,u^{-1}.\,$ So to find such a scaling we solve for a scaling that maps $\,5x \to 3x,\,$ ie. $\,5u\equiv 3 \iff u\equiv 5/3\equiv -20/3\equiv -4,\,$ and it works since $\,-4(-7y)\equiv 5y.$

Alternatively, geometrically, we can show these lines are equal since they have the same slope $\,y/x\,$ and same point $\,(0,0).\,$ Note that $x\equiv 0\iff y\equiv0\,$. Else $\ x\not\equiv 0\,$ so $\,7y\equiv 5x\iff y/x\equiv 5/7,\,$ and $\, 5y\equiv -3x \iff y/x\equiv -3/5.\,$ These slope fractions $\,\frac{5}7,\, \frac{-3}5\,$ are equal (i.e. congruent $\rm mod\ 23)\,$ because cross multiplication yields that $\, 5(5)\equiv 2\equiv 7(-3)\pmod{23}.$

Here the geometry and linear algebra works as usual since we are working over a coefficient ring that is a field $\,\Bbb Z/23 = $ integers mod $\,23,\,$ i.e. $\,a\not\equiv 0\,\Rightarrow\, a\,$ is a unit (invertible).

Divisibility questions are often simpler when rephrased as modular arithmetic. You want to show

$$ 3x + 5y \equiv 0 \pmod{23} \implies 5x - 7y \equiv 0 \pmod{23} $$

A simplistic thing to do is to look at the known equation, and simplify it by solving for $x$

$$ x \equiv 3^{-1} \cdot (-5) y = 6y \pmod{23} $$

and using this to eliminate $x$ from the thing we're trying to prove:

$$ \begin{align} 5x - 7 \equiv 0 \pmod{23} &\iff 5(6y) - 7y \equiv 0 \pmod{23} \\&\iff 30y - 7y \equiv 0 \pmod{23} \\&\iff 0y \equiv 0 \pmod{23} \end{align}$$

Conveniently, we've accidentally solved the problem in the process of simplifying it!

Another thing to do with it is to use your linear algebra. The set of all solutions for $(x,y)$ in the equation $3x + 5y \equiv 0 \pmod{23}$ is a one-dimensional vector space over the field of 23 elements. Similarly, the set of all solutions to $5x - 7y \equiv 0 \pmod{23}$ is a one-dimensional vector space.

If every solution to the former is truly a solution to the latter, then those have to be the same one-dimensional vector space. And for that to happen, the vectors $(3, 5)$ and $(5, -7)$ must be linearly dependent.

We could try to see that one of these vectors is a multiple of the other one, but it is even easier (no modular division involved!) to check the determinant of the matrix

$$ \left[ \begin{matrix} 3 & 5 \\ 5 & -7 \end{matrix} \right]$$

is zero. And indeed,

$$3 \cdot (-7) - 5 \cdot 5 = -21 - 25 = -46 \equiv 0 \pmod{23} $$

It is important that $23$ is prime; linear algebra is a bit more subtle if you try to work in the ring of integers modulo a composite number.