Finding Modular Multiplicative Inverses (Quickly!)

Question

as part of an upcoming number theory exam I will need to find the modular multiplicative inverse of every element of ${Z_n}$ (the ones that exist anyway) very quickly. The only way I know is using the Extended Euclidean Algorithm. Is there no way that is faster? The question isn't worth many marks but will take an inordinate amount of time.

Answer 1

What I'm talking about in my comment is a "two-column" form that goes like this:

We want to compute the inverse of $7$ in $\mathbb{Z}_{23}$. We write the numbers $23$ and $7$ in the first two lines of the first column, then $0$ and $1$ in the right column.

\begin{array}{|c|c|} \hline \text{I.} \quad 23 & 0 \\ \text{II.} \quad 7 & 1 \\\hline \end{array}

Then start subtracting equations from each other, until you have $1$ left in the left column. And always update the right side, too.

\begin{array}{|c|c|} \hline \text{I.}\quad \quad\quad 23 & 0 \\ \text{II.} \quad\quad\quad 7 & 1 \\ \text{III=I - 3II} \quad 2 & -3 \\ \text{II-3III} \quad\quad 1 & 10 \\\hline \end{array}

First, I subtracted 3 times the second row from the first row, because $7$ goes a full $3$ times into $23$. Thus on the right column I have $0 - 3\cdot1 = -3$. Then, With $7$ and $2$ in the next rows, I subtract the third line three times from the second line, because 2 goes into 7 a full 3 times. Then $7 - 3\cdot2 = 7 - 6 = 1$, and on the right column $1 - 3\cdot(-3) = 1 - (-9) = 10$. Once you reach the $1$ in the left column, the inverse of the number is on the right. If you don't reach a $1$, that means the inverse doesn't exist because the number and the modulus aren't co-prime.

And as such $$7^{-1} \equiv 10 \mod{23} $$

In my exams I had to calculate inverse for a maximum $n \leq 50$ without a calculator.

Answer 2

If $n$ is not large, then you can take one number coprime with $n$ and compute its powers mod $n$ until you get to $1$. This gives you the inverses of all elements you encounter in this cycle. Then take the next element not in this cycle and repeat.

Answer 3

Solve $ax \equiv 1 \pmod{n}$

I would tackle these problems keeping this trick in mind and applying the basic tactic of making $a$ smaller by 'multiplying to the modulus'.

Example 1: Solve $12x \equiv 1 \pmod{19}$.
$\; 12x \equiv 1 \pmod{19} \; \text{ iff}$
$\; -7x \equiv 1 \pmod{19}$

and

$\;-7 \cdot (3) \equiv -21 \equiv -2 \pmod{19}$
$\;-2 \cdot (9) \equiv -18 \equiv 1 \pmod{19}$

and therefore the solution is given by $x \equiv 3 \cdot 9 \equiv 8 \pmod{19}$.

Example 2: Solve $67x \equiv 1 \pmod{97}$.
$\; 67x \equiv 1 \pmod{97} \; \text{ iff}$
$\; -30x \equiv 1 \pmod{97}$

and

$\;-30 \cdot (3) \equiv -90 \equiv 7 \pmod{97}$
$\;7 \cdot (14) \equiv 98 \equiv 1 \pmod{97}$

and therefore the solution is given by $x \equiv 3 \cdot 14 \equiv 42 \pmod{19}$.

Example 3: Solve $7x \equiv 1 \pmod{23}$.

$\;7 \cdot (4) \equiv 5 \pmod{23}$
$\;5 \cdot (5) \equiv 2 \pmod{23}$
$\;2 \cdot (12) \equiv 1 \pmod{23}$

and therefore the solution is given by $x \equiv 4 \cdot 5 \cdot 12 \equiv 10 \pmod{23}$.

Example 4: Solve $6x \equiv 1 \pmod{10}$.
$\; 6x \equiv 1 \pmod{10} \; \text{ iff}$
$\; -4x \equiv 1 \pmod{10}$

and

$\;-4 \cdot (2) \equiv 2 \pmod{10}$
$\;2 \cdot (5) \equiv 0 \pmod{10}$

If $6x \equiv 1 \pmod{10}$ then $5 \cdot (6x) \equiv 5 \pmod{10}$, so there are no solutions.