# Find inverses in a cyclic group

I have come up with the following question/problem and want to try to understand and solve it.

Basically, given a cyclic group $$G = \mathbb{Z}_{59}^{\times}$$; find inverse of $$31$$ in this group.

Now, I understand that $$\mathbb{Z}^{\times}$$ in a cyclic group implies that it is multiplicative but then how do I expand the cyclic group? More importantly, how do I find inverses of a number in a group say $$31$$?

We have that $$\text{gcd}(31,59) = 1$$. Now use the extended euclidean algorithm to find the Bezout coefficients to get $$1 = 31a + 59b$$ for some integers $$a$$ and $$b$$. This means that you get $$1 = 31 \cdot a$$ mod $$59$$, i.e. $$a$$ mod $$59$$ is the inverse of $$31$$ mod $$59$$.

As you asked for the computation:

We have

$$59 = 1 \cdot 31 + 28$$

$$31 = 1 \cdot 28 + 3$$

$$28 = 9 \cdot 3 + 1$$

$$3 = 1 \cdot 3 + 0,$$

which once again shows that $$\text{gcd}(59,31) = 1$$. We now get

$$\small 1 = 28 - 9 \cdot 3 = 28 - 9(31- 28) = -9 \cdot 31 + 10 \cdot 28 = -9 \cdot 31 + 10(59 - 31) = 10 \cdot 59 -19 \cdot 31,$$ i.e. $$a = -19$$ and $$b = 10$$. Thus $$\overline{-19} = \overline{40}$$ is the inverse of $$\overline{31}$$.

Let me also add a concrete description of the group. Consider $$\mathbb{Z}/n\mathbb{Z} = \lbrace \overline{0},\overline{1},\dots,\overline{n-1} \rbrace$$. Then we get $$\mathbb{Z}/n\mathbb{Z}^{\times} = \lbrace \overline{k} \mid \text{gcd}(k,n) = 1\rbrace$$. In the case that $$n$$ is prime (as in your example) this yields $$\mathbb{Z}/n\mathbb{Z}^{\times} = \lbrace \overline{1},\dots,\overline{n-1} \rbrace = (\mathbb{Z}/n\mathbb{Z})\setminus\lbrace \overline{0} \rbrace$$.

• Thanks for providing an answer. Just a few questions, why did you jump/do the gcd(31,59)? Also how do you know that the gcd is 1? I assume it is because they are both prime numbers right? Aug 13, 2019 at 0:30
• Also, how do I expand the group? It is all interesting stuff but also complex to understand which is why I was hoping that an example of my own making would help me better understand cyclic groups in general. Would definitely make my day if I understood it!!! Aug 13, 2019 at 0:32
• The extended euclidean algorithm allows you to get such an equation for the gcd. Therefore it was important that the gcd is $1$. Yes. The gcd is $1$ since $31$ (actually also $59$) is a prime number. One of them being prime is enough though as $31 \neq 59$.
– Con
Aug 13, 2019 at 0:33
• What do you mean by ”expand the group“? Do you want a concrete description of it?
– Con
Aug 13, 2019 at 0:35
• I see, so what you are saying is that so long as one of the numbers are prime then the gcd is 1? I don't suppose you could kindly help with expanding the cyclic group? Aug 13, 2019 at 0:35