# Order of elements in $Z_n$

I have this question:

Let $x, n$ be integers with $n \geq 2$ and $n$ not dividing $x$. Show that the order o($\bar{x}$) of $x \in Z_n$ is
$o(\bar{x})= \frac{n}{HCF(x, n)}$

I’ve been thinking about it for ages but I still don’t get why. A hint would be appreciated.

#### Solutions Collecting From Web of "Order of elements in $Z_n$"

Hint: $\gcd(x,n) \cdot \operatorname{lcm}(x,n)=nx$.

Hint $\$ Denote $\rm\:gcd(x,y)\:$ by $\rm\:(x,y),\:$ and $\rm\:lcm(x,y)\:$ by $\rm\:[x,y].\$ Below are two proofs.

$(1)\ \ \begin{eqnarray}\rm kx\equiv 0\iff n\mid kx \iff n\mid kx,kn\iff n\mid (kx,kn)=k\, (x,n)\iff n/(x,n)\mid k \end{eqnarray}$

$(2)\ \ \begin{eqnarray}\rm kx\equiv 0\iff n\mid kx \iff x,n\mid kx\iff [x,n]\mid kx \iff [x,n]/x\mid k\iff n/(x,n)\mid k\end{eqnarray}$

where the last $\iff$ employs the fundamental $\rm\:lcm * gcd\:$ law: $\rm\: [x,n](x,n)\, =\, xn$.