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!
$\endgroup$2 Answers
$\begingroup$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.
$\endgroup$ 3 $\begingroup$Use extended Euclidean algorithm to find
$$9a + 101b = GCD(9, 101) = 1$$
If you multiply both sides with 58, you get
$$ 9(58a) + 101(58b) = 58$$
And so $58a$ would be the $x$ you wish to find. To get all general solutions, find the $LCM(9,101)$: $$9\cdot101 = 101\cdot9 = LCM(9,101)\\ 9\cdot101-101\cdot9 = 0$$
And so generally $x= 58a + 101n$ is also a solution.
Notice, this method does not require $p$ to have an inverse in general to solve $px\equiv q\pmod{n}$. For example, you can as well solve $9x\equiv60\pmod{102}$.
$\endgroup$ 4
