2
$\begingroup$

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$?

$\endgroup$

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
25
  • $\begingroup$ 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? $\endgroup$ Aug 13, 2019 at 0:30
  • $\begingroup$ 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!!! $\endgroup$ Aug 13, 2019 at 0:32
  • $\begingroup$ 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$. $\endgroup$
    – Con
    Aug 13, 2019 at 0:33
  • $\begingroup$ What do you mean by ”expand the group“? Do you want a concrete description of it? $\endgroup$
    – Con
    Aug 13, 2019 at 0:35
  • $\begingroup$ 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? $\endgroup$ Aug 13, 2019 at 0:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .