I'm interested in solving the following equation:
$$9x\equiv 58 \pmod{101}$$
Meaning taking $\pmod{101}$ of $9 \times$ some number $x$ will equal $58$. I know how to solve this using a table—in class, we were told we should start by plugging in values for x, starting with 0, like so:
\begin{array}{c|c|c}
x & 0 & 1 & 2 \\
\hline
9x-58 \pmod{101} & -58 & -49 & -40
\end{array}
and then take $\pmod{101}$ of each $f(x)$ until a zero was obtained. However, this method seems somewhat impractical for large numbers. For instance, I looked online and found the answer to my question is $x=85$. Is there some way to find the answer quicker? I know how to use the Extended Euclidean Algorithm; not sure if it would aid in this instance. Thanks!
Best Answer
You are correct that the extended Euclidean algorithm is the best tool here. Try finding integers $x$ and $y$ for which
$$9x + 101 y = 58$$
This is possible since $9$ and $101$ have greatest common divisor $1$, so a solution to $9a + 101b = 1$ can be found. Then $x$ will be the desired solution.