Inverse of $3$ in multiplicative group $C_{20}.$

98 Views Asked by At

Kindly vet and guide:

First of all can we consider a cyclic group as both : multiplicative and additive group.

Say, $C_n$ has at least two generators $g, g^{n-1}$ and though composition adds exponents, but group operation is multiplication.

To take as additive group, need consider the fact that $C_n\cong \mathbb{Z_n}.$

Request reference source text, as for this have relied on lines stated as part of answer here only.

Second, if can consider as multiplicative group; then how to use Bezout lemma to find inverse, as shown here.

Say, find Inverse of $3$ in multiplicative group $C_{20}.$

$3x + 20y= 1,$ Have a doubt that $x,y \in \mathbb {Z}$ rather than $\in \mathbb {Z} / 20\mathbb{Z}.$

$$\begin{align}&20= 3\cdot 6+2\\& 3=2\cdot 1+1\end{align}$$

Now, taking reverse, have:

$$1= 3-2\cdot 1,$$ $$1= 3-(20-3\cdot 6)\cdot 1$$ But, unable to proceed.

1

There are 1 best solutions below

8
On BEST ANSWER

I am going to answer of your original question.

Let $U(20) $ be the multiplicative group of $C_{20}$.

We have $3\in U(20)$. What is the inverse of $3$ in $U(20) $?


Suppose $3^{-1}=x$. Then $3x\equiv 1\pmod{20}$. We have $1=3-(20-3\cdot 6)=3\cdot 7-20$. Hence $3\cdot 7\equiv 1\pmod{20}$. Hence $x=7$ is the required inverse of $3$. You can recheck your work: $3\cdot 7\pmod{20}=21\pmod{20} =1$.


Another approach: $(3, 20) =1$ . Hence by F.L.T $3^{\varphi(20)} \equiv 1\pmod{20}$, which implies $3^8\equiv 1 \pmod{20}.$ But

$$\begin{align}3^{-1}&\equiv 3^{-1}\cdot 3^8 \pmod{20}\\ &\equiv 3^7\pmod{20} \\ & \equiv3^43^3 \pmod{20}\\ & \equiv 7\pmod{20}. \end{align}$$