2

$$7x + 9y \equiv 0 \pmod {31}$$

$$2x - 5y \equiv 2 \pmod {31}$$

I'm supposed to find the x, but I'm stuck in the middle. First I tried to get rid of y.

$$53x \equiv 18 \pmod {31}$$

Here now I don't know what to do with this. Can anyone help me out?Thanks.

Stefan4024
  • 35,843
More Code
  • 221

1 Answers1

5

You need to find the inverse of $53\equiv 22$ modulo $31$. To do it, you may use the Euclidean algorithm. ote you can also look at this as a $$\begin{pmatrix}7&9\\2&-5\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}0\\2\end{pmatrix}$$

Note that $$\det\begin{pmatrix}7&9\\2&-5\end{pmatrix}=-53\equiv 9$$

But $9\times 7=63\equiv 1$ so

$$\begin{pmatrix}x\\y\end{pmatrix}=7\begin{pmatrix}-5&-9\\-2&7\end{pmatrix}\begin{pmatrix}0\\2\end{pmatrix}=\begin{pmatrix} 29\\23\end{pmatrix}$$

That is, one can work as usual using Cramer's rule as long as $\det A\not \equiv 0$ modulo what you're working in.

Pedro
  • 122,002
  • How so? Why am I finding the inverse of 53 = 22 modulo 31? – More Code Oct 02 '13 at 22:50
  • When you have an equation of the form $ax=b$; how do you "find" $x$? You divide by $a$, right? Here, we can also "divide" since $31$ is prime, meaning every nonzero number has an inverse, that is, if $31\not\mid x$ then we can find $y$ such that $xy\equiv 1\mod 31$. If you find this number, you can find what $x$ is. – Pedro Oct 02 '13 at 22:53
  • 2
    In this case, and almost always with small numbers, there are tricks. Note that $53\equiv -9\pmod{31}$. So we are solving $-9x\equiv 18$, which gives $x\equiv -2\equiv 29$. – André Nicolas Oct 02 '13 at 23:08