Very basic question, but how can I solve this? $7x+9y \equiv 0 \bmod 31$ and $2x-5y \equiv 2 \bmod 31$.
Asked
Active
Viewed 72 times
1
-
1First find two numbers $a$ and $b$ such that $7a+9b = 1 = gcd(7,9)$. The second one is similar. – Prahlad Vaidyanathan Sep 23 '13 at 02:21
2 Answers
2
You can write it as $$\begin{pmatrix}7&9\\2&-5\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}0\\2\end{pmatrix}$$
Invert the matrix, but in $\Bbb Z_{31}$, which is a field.
Pedro
- 122,002
-
How do I use inverted matrices to solve? I'm learning this in a CS class, so they didn't really talk about matrices-I'm familiar with them, just not with what you're suggesting. Take the inverse of the LHS matrix, then what? – Sep 23 '13 at 04:55
-
@Tony Then multiply on the left by the vector on the right of the equation. – Pedro Sep 23 '13 at 21:03
1
Adding to Peter's answer, if you're asked to solve this by hand, this particular modular arithmetic is easy because $31$ is prime. Multiplication and addition tables fall out very easily and the only part where you'd be required to do some computation is when you find the inverse of a number.
Sudarsan
- 876