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$?
 A: 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$.
