Krdytkyu

Recently I asked how to calculate the order of an element in $U_{27}=mathbb{Z}_{27}^*$ (Multiplicative group of integers modulo $27$) (link). Problem is I still don't understand the material but I would like to explain what I know and what I don't. Tried to find some similar thread on the same topic and I found the following tread (link). Although it does not answer my question directly, it points into that direction. I know the hard way to find the order of an element in $U_{27}$. For example in order to find the order of $5$ in $U_{27}$ I would do:
$$begin{align*}
5&=5bmod 27=5\
5^2&=25bmod 27=25\
5^3&=125bmod 27=17
end{align*}$$

And so on, until I find $ninmathbb{N}$ so $5^n=1$. It could take awhile, in fact I know that the order of $5$ in $U_{27}$ is $18$ ($5^{18}=3814697265625(mod27)=1$), so I will have to calculate $18$ times and facing some big numbers. I think that there is a fast way using the euler function. How can I use it in my advantage? is there a formula?

First of all note that,

• if $G$ is group and $ain G$ then $o(a)=o(a^{-1})$.



• 
  

  if $G$ is group and $ain G$ be an element of order $m$ then $o(a^k)=frac{m}{gcd(m,k)}$ where $kin mathbb{N}$

  
  
  

  By using these two results you can avoid half of calculation needed to compute order of elements.

  
  

Now let's start,

$o(1)= 1$ since $1$ is identity in $U_{27}$.

$o(2)= 18$ since $2^{18}≡1mod 27$
and $2^m ≢ 1mod 27$ for $m<18 in mathbb{N}$. Now using our above results:

$o(4)=o(2^2)=frac{o(2)}{gcd(o(2),2)}=frac{18}{gcd(18,2)}=frac{18}{2}=9$

$o(8)=o(2^3)= frac{o(2)}{gcd(o(2),3)}=frac{18}{gcd(18,3)}=frac{18}{3}=6$

Similarly you can compute easily, $o(16)=o(2^4)$, $o(5)=o(2^5)$, $o(10)=o(2^6)$, $o(20)=o(2^7)$, $o(13)=o(2^8)$ etc. in fact order of all elements in $U_{27}$ can be computed just by using above second result.(because as $2$ is generator in $U_{27}$ and hence it will generate all elements)

To see how first result work: as we know $[2•14]_{27}=[14•2]_{27}=[1]_{27}$ so $2$ and $14$ are inverses in $U_{27}$ and hence $o(14)=o(2)=18$

Here $U_{27}$ is a cyclic group of order $18=2 times 3^2$ . Note that if $g$ generates $U(p^2)$ then $g$ generates $U(p^k),k geq 2$ as well! where $p$ is an odd prime. [For a proof of this, refer this paper, Lemma $3(2)$]

Here $langle5 rangle= U(9) $ and so $langle 5 rangle= U(3^k) ,k geq 2$ and in particular $langle 5 rangle= U(3^3)=U(27) $, so $vert 5 vert =18$