# Approaching modular arithmetic problems

I'm a little stumbled on two questions.

How do I approach a problem like $x*41 \equiv 1 \pmod{99}$.

And given $2$ modulo, $7x+9y \equiv 0 \pmod{31}$ and $2x−5y \equiv 2 \pmod{31}$ (solve for $x$ only)?

When I solve for $x$ for the latter, I got a fraction as the answer and I'm not sure if I can have a fraction as an answer? I'm not sure how to approach the first problem either.

• What fraction did you get as answer? – Git Gud Sep 22 '13 at 22:20
• The first problem involves inverses. What is the inverse of 41 mod 99? The second problem is a set of linear equations in $x$ and $y$ modulo 31, which means the two can be added/subtracted/etc. as if they were a set of normal equations looking for a linear solution. – abiessu Sep 22 '13 at 22:25

Finding the solution to $$x \times 41 \equiv 1 \pmod {99}$$ is equivalent to asking for the multiplicative inverse of $41$ modulo $99$. Since $\gcd(99,41)=1$, we know $41$ actually has an inverse, and it can be found using the Extended Euclidean Algorithm:

\begin{align*} 99-2 \times 41 &= 17 \\ 41-2 \times 17 &= 7 \\ 17-2 \times 7 &= 3 \\ 7-2\times 3 &= 1 &=\gcd(99,41). \\ \end{align*} Going back, we see that \begin{align*} 1 &= 7-2\times 3 \\ &= 7-2\times (17-2 \times 7) \\ &= 5 \times 7-2\times 17 \\ &= 5 \times (41-2 \times 17)-2\times 17 \\ &= -12 \times 17+5 \times 41 \\ &= -12 \times (99-2 \times 41)+5 \times 41 \\ &= 29 \times 41-12 \times 99 \\ \end{align*} Hence $29 \times 41 \equiv 1 \pmod {99}$ and thus $x=29$.

In the second case, we have $$7x+9y \equiv 0 \pmod {31}$$ and $$2x-5y\equiv 2 \pmod {31}.$$ Here we want to take $7x+9y=0 \pmod {31}$ and rearrange it to get $x \equiv ?? \pmod {31}$, then substitute it into the other equation and solve for $y$. This requires finding the multiplicative inverse of $7$ modulo $31$ (which we can do as above). It turns out $7 \times 9 \equiv 1 \pmod {31}$. Hence \begin{align*} & 7x+9y=0 \pmod {31} \\ \iff & 7x \equiv -9y \pmod {31} \\ \iff & x \equiv -9y \times 9 \pmod {31} \\ \iff & x \equiv 12y \pmod {31}. \end{align*} We then substitute this into the equation $2x-5y\equiv 2 \pmod {31}$, which implies $$2 \times 12y-5y \equiv 2 \pmod {31}$$ or equivalently $$19y \equiv 2 \pmod {31}.$$ Yet again, we find a multiplicative inverse, this time of $19$ modulo $31$, which turns out to be $18$. So \begin{align*} & 19y \equiv 2 \pmod {31} \\ \iff & y \equiv 2 \times 18 \pmod {31} \\ \iff & y \equiv 5 \pmod {31}. \end{align*} Hence $$x \equiv 12y \equiv 29 \pmod {31}.$$ Thus we have the solution $(x,y)=(29,5)$.

• Are you sure the answer to the first part is x=20? – Mufasa Sep 22 '13 at 22:35
• Thanks for point that out; it was an arithmetic error (actually, I found the inverse mod 91 by mistake) and it should be fixed now. – Rebecca J. Stones Sep 22 '13 at 22:47
• You're welcome. BTW: I am learning a lot from your posts - so THANK YOU! :) – Mufasa Sep 22 '13 at 22:49

For the first one, you could approach it as follows:
$41x=1$ mod $99$
$140x=1$ mod $99$ (because 41 mod 99 = (41+99) mod 99)
$140x=100$ mod $99$ (because 1 mod 99 = (1+99) mod 99)
$7x=5$ mod $99$ (divide both sides by 20)
$7x=203$ mod $99$ (because 5 mod 99 = (5+99+99) mod 99)
$x=29$ mod $99$ (divide both sides by 7)

For the first one, you have to find a multiplicative inverse for $41$ mod $99$. Use Euclid's algorithm to find the solutions of $41\cdot x + 99 \cdot y = 1$ to find $x$.

Are you familiar with abstract algebra? If yes, do you know that $\mathbb{Z}_{31}$ is a field because $31$ is a prime number and you can use tools of linear algebra because it works overy any field?

You have the following system of equations in $\mathbb{Z}_{31}$:

$$7x+9y=0$$ $$2x-5y=2$$

You can use Gaussian elimination in $\mathbb{Z}_{31}$ to find $x$ and $y$. But you have to be careful that your coefficients are in $\mathbb{Z}_{31}$ not in $\mathbb{R}$.

EDIT(suggested by Git Gud):

Notice that if you get a fraction like $\displaystyle \frac{a}{b}$ then you should think of it as $a \cdot b^{-1}$ and then find $b^{-1}$ in $\mathbb{Z}_{31}$. As previously said, $\mathbb{Z}_{31}$ is a field, so talking about fractions in it makes sense. The notation $\frac{a}{b}$ is actually nothing but $a.b^{-1}$ where $.$ denotes the multiplication in the field and $b^{-1}$ denotes the multiplicative inverse of $b$ in the field.

• @GitGud: OK. Done. – user66733 Sep 22 '13 at 22:32