1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Maximilian Gerhardt May 21 '16 at 12:35
  • $\begingroup$ @Maximilian Gerhardt: A four-column form, I'd say… $\endgroup$ – Bernard May 21 '16 at 12:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Olim May 21 '16 at 12:40
  • 1
    $\begingroup$ How large do you expect $n$ to be? $\endgroup$ – lhf May 21 '16 at 12:44
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.