I could really use some help here:
Prove that $17|2x+3y\iff 17|9x+5y$.
I don't even know how to start. Just pointing me at a similar problem that has a full solution would be helpful enough, but of course I will be extremely thankful if someone could explain how to approach solving this! :)
Answer
Let's see the problem in terms of linear algebra.
Let $u=(2,3)$, $v=(9,5)$, and $w=(x,y)$. These are vectors in $\mathbb F_{17}^2$.
Then, $17\mid 2x+3y\iff 17\mid 9x+5y$ iff $\langle u,w \rangle = 0 \iff \langle v,w \rangle = 0 $, and this happens iff $u^{\perp} = v^{\perp}$, which happens iff $u$ and $v$ generate the same subspace, that is, are linearly dependent.
Therefore, you want to prove that the vectors $(2,3)$ and $(9,5)$ are linearly dependent over $\mathbb F_{17}$. This is easy, because
$$
\begin{vmatrix} 2 & 3 \\ 9 & 5 \end{vmatrix} = -17 \equiv 0 \bmod 17
$$
If you want do it explicitly, find $a$ such that $a(2,3)=(9,5)$ by solving
$$
2a \equiv 9 \bmod 17, \quad 3a \equiv 5 \bmod 17
$$
and hope to get the same solution. Indeed, the solution is $a=-4$.
No comments:
Post a Comment