Consider the space $\mathbb{Z}_n$, where $n$ is a reasonably large prime, say, for example, 53. How can I quickly and efficiently write out the multiplicative inverses for each element of $\mathbb{Z}_{53}$? I don't want to use the Extended Euclidean algorithm 26 times (for the 52 total terms in this set). Is there a way to do this that's not just "brute force", so to speak?
To be clear, I want to do this by hand, not using a computer.
Best Answer
Let $[a]$ be a residue class modulo the prime $p$ and let $[b] = [a]^{-1}$ be its multiplicative inverse. You can, for instance, find this inverse using the extended Euclidean algorithm. Then, \begin{align*} [a^2]^{-1} &= [b^2] \text{,} \\ [a^3]^{-1} &= [b^3] \text{,} \\ &\vdots \end{align*} So use the slow method to get one result, then go through successive powers to fill in more entries in your table of inverses. At some point, the powers cycle back, perhaps not filling in the entire table. Now pick one of the unfilled entries and start this process again. When you run out of empty entries, hooray!, you're done.
One interesting thing that can happen is that you can in one step work out the inverses of the powers of $[c^2]$. At a later step, you find you are working out the powers of $[c]$ because every even power is already in your table and every (or possibly most) odd powers are new entries. (Some entries may already be filled in as members of other cycles.)
As an example, modulo $17$, $[2]^{-1} \cong [9]$, so \begin{align*} [2^2]^{-1} \cong [4]^{-1} &\cong [9^2] \cong [13] \\ [2^3]^{-1} \cong [8]^{-1} &\cong [9\cdot 13] \cong [15] \\ [2^4]^{-1} \cong [16]^{-1} &\cong [9\cdot 15] \cong [16] \\ [2^5]^{-1} \cong [15]^{-1} &\cong [9 \cdot 16] \cong [8] \\ [2^6]^{-1} \cong [13]^{-1} &\cong [9 \cdot 8] \cong [4] \\ [2^7]^{-1} \cong [9]^{-1} &\cong [9 \cdot 4] \cong [2] \\ [2^8]^{-1} \cong [1]^{-1} &\cong [9 \cdot 2] \cong [1] \\ [2^9]^{-1} \cong [2]^{-1} &\text{and we've cycled.} \end{align*} Note that $2^8 \cong 1$ was a slightly earlier signal that we were about to cycle.
Notice we got half of the entries for the table. Now try it with $[3]$ and (I think) get the other half (or go around again with another new starting point).
There is a theoretical idea floating around in the above: primitive roots. Pulling a primitive root out of thin air is hard, so here, we just hope that we either picked a primitive root or picked a small power of a primitive root so we can fill in many table entries. Even if you don't, you get some table entries.
We could probably estimate the expected number of cycles to complete the table, which probably has a leading term of the approximate size $\frac{\varphi(p)}{\varphi(\varphi(p))}$, where $\varphi$ is the Euler totient function, to capture the number of residue classes that are a small power of one of the primitive roots modulo $p$.