# Finding Modular Multiplicative Inverses (Quickly!)

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.

• Can you show us an example of how you use the EEA? There is basically a two-column form, that's the fastest method known to me. – Maximilian Gerhardt May 21 '16 at 12:35
• @Maximilian Gerhardt: A four-column form, I'd say… – Bernard May 21 '16 at 12:36
• My issue was that I had to do it multiple times but of course what I hadn't thought of was the symmetry involved. For example, if looking mod 18, you need to find inverses of 1, 5, 7, 11, 13, 17. 1 and 17 are trivial, and the remaining 4 pair up as inverses so you only really have to solve 2 of them. Can I delete this question? To any moderators reading, this question can be deleted. – Olim May 21 '16 at 12:40
• How large do you expect $n$ to be? – lhf May 21 '16 at 12:44

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.

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