$$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.


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.

  • $\begingroup$ How so? Why am I finding the inverse of 53 = 22 modulo 31? $\endgroup$
    – More Code
    Oct 2 '13 at 22:50
  • $\begingroup$ 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. $\endgroup$
    – Pedro Tamaroff
    Oct 2 '13 at 22:53
  • 2
    $\begingroup$ 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$. $\endgroup$ Oct 2 '13 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.