# What is the easiest way to find multiplicative inverse of $\mathbb{Z}_5$ field

What is the easiest way to find multiplicative inverse of $\mathbb{Z}_5$ field

$\mathbb{Z}_5=\{0,1,2,3,4\}$

To show that this is a field, I have to show that for all $z\in\mathbb{Z}_5$, they all have multiplicative inverses and additive inverses.

I know how to obtain them, but I'm looking for a pattern.

\begin{array}{|c|c|c|c|} \hline of& 0 & 1 & 2 & 3 & 4 \\ \hline is& 0& 4& 3 & 2 & 1\\ \hline \end{array}

The additive inverse of $0$ is $0$, inv of $1$ is $4$. There's a pattern, start with zero, then put the largest number, then go downwards until 1

But for multiplicative inverses the pattern is odd.

\begin{array}{|c|c|c|c|} \hline of& 0 & 1 & 2 & 3 & 4 \\ \hline is& none& 1& 3 & 2 & 4\\ \hline \end{array}

I don't really see a pattern, and I want to know if there is one. My question asks me to find if $\mathbb{Z}_{11}$ is a field (it is), but I have to find all the multiplcative inverses and this is tiring without a pattern.

Let $k \in \Bbb Z_p \setminus \{0\}$ with $p$ prime. We know that $k^p=k$ from Fermat's little theorem. Multiply both sides by $k^{-2}$ to get $k^{p-2}=k^{-1}$.

• I'm not sure I understand 100%. In our case $p=5$, and suppose we want inv of $k=2$, so we do $2^{5-2}=2^{3}=8$, which is not the inverse? Sep 9, 2017 at 16:26
• @KSplitX You're supposed to modulo the result by $p$ ($2^3=3$ is valid as $2$ is an element of $\Bbb Z_5$ and $4\times2$ is defined to be $3$ inside $\Bbb Z_5$) Sep 9, 2017 at 16:32

For $z \in \mathbb{Z}_p \backslash\{0\}$ with $p$ prime you have $\gcd(z,p) = 1$, so you can write $$az + bp = 1$$ with integers $a,b$. Modulo $p$ this gives $az = 1$.

• I'm not sure I understand. What is the pattern? You gave me a method of calculating it, but is there a pattern persay? Sep 9, 2017 at 16:23
• I think this largely depends on what you mean by "a pattern". The pattern is that the inverse of $z$ is the coefficient $a$ in the formule $az + bp = 1$. Sep 9, 2017 at 16:29

If you really want to see a "pattern" then you need to write the multiplicative group down in "cyclic order" as powers of two: $2^0=1$, $2^1=2$, $2^2=4$, $2^3=8=3$, back to $2^4=1$. Then the inverses go in the opposite order $2^{-0}=1$, $2^{-1}=2^3$, $2^{-2}=2^2$, $2^{-3}=2^1$.

So in table format

$$\begin{array}{|c|c|c|c|} \hline \text{of}& 0 & 1 & 2 & 4 & 3 \\ \hline \text{is}& \not\exists& 1& 3 & 4 & 2\\ \hline \end{array}$$

or

$$\begin{array}{|c|c|c|c|} \hline \text{of}& 0 & 1 & 2 & 4 & 3 \\ \text{power form}&\not\exists&2^0&2^1&2^2&2^3\\ \hline \text{is}& \not\exists& 1& 3 & 4 & 2\\ \text{power form}&\not\exists&2^4&2^3&2^2&2^1\\ \hline \end{array}$$

Every finite field has so called primitive elements (at least one) $g$ such that all the non-zero elements of the field are of the form $g^i$ with $g=0,1,2,\ldots,q-2$ where $q$ is the number of elements of the fields. Here $g^0=g^{q-1}=1$. The above table was based on the choice $g=2$, but we could have used $g=3$ equally well. For the field $\Bbb{Z}_7$ we can use $g=3$ or $g=5$, for the field $\Bbb{Z}_{11}$ we can use $g=2$. Finding a primitive element is not always trivial, and there are difficult open questions. For example, it is not known whether $g=2$ is a primitive element of the field $\Bbb{Z}_p$ for infinitely many primes $p$. See Artin's conjecture.

To answer the question in the title. The extended Euclidean algorithm is the simplest to understand, fast method for finding inverses in fields of the form $\Bbb{Z}_p$. Basically it is a quick method for finding the integers $a,b$ that appear in Elvorfirilmathredia's answer. For heaven's sake don't try to find a primitive element and build tables like those above when $p$ is, say, a hundred digit prime :-)

There is no way to even "approximate" the difference between $1/x$ and a "linear pattern" like $ax+b$ ("approximate" in a sense that I would need to spend a few hours talking about). Basically, in average the "error" is jumping all over the place. The way I would quantify this claim would be based on Kloosterman sums.