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