1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What fraction did you get as answer? $\endgroup$ – Git Gud Sep 22 '13 at 22:20
  • $\begingroup$ 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. $\endgroup$ – abiessu Sep 22 '13 at 22:25
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are you sure the answer to the first part is x=20? $\endgroup$ – Mufasa Sep 22 '13 at 22:35
  • $\begingroup$ 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. $\endgroup$ – Rebecca J. Stones Sep 22 '13 at 22:47
  • 1
    $\begingroup$ You're welcome. BTW: I am learning a lot from your posts - so THANK YOU! :) $\endgroup$ – Mufasa Sep 22 '13 at 22:49
1
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @GitGud: OK. Done. $\endgroup$ – user66733 Sep 22 '13 at 22:32

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.