Find and prove a formula for the order of an element $k\in\mathbb Z_n$ I've looked at the orders of all of the elements in the group $\mathbb Z_{12}$ and from that guessed a formula that might be right: $$\mid k\mid =\frac{n}{hcf(k,n)}$$ where $\mid k \mid$ denotes the order of the element $k$ and $hcf(k,n)$ denotes the highest common factor of $k$ and $n$. Is this formula correct? And if so, how would I prove it?
 A: Your formula is correct.
What you want is the smallest positive number $|k|$ so that $|k|\cdot k$ is a multiple $j\cdot n$ of $n$. The number $|k|\cdot k = j\cdot n$ is called the least common multiple of $n$ and $k$, or $\operatorname{lcm}(n, k)$ for short.
It is a common exercise in beginning number theory to show that $\operatorname{lcm}(a, b)\cdot \operatorname{hcf}(a, b) = ab$ for any two positive integers $a$ and $b$. We get, for $n$ and $k$:
$$
\operatorname{lcm}(n, k)\cdot \operatorname{hcf}(n, k) = n\cdot k\\
\operatorname{lcm}(k, n) = \frac{n\cdot k}{\operatorname{hcf}(n, k)}\\
|k|\cdot k = \frac{n\cdot k}{\operatorname{hcf}(n, k)}
$$
and if you divide each side by $k$, you get your formula.
A: You are right. You can also prove a more general result.
Question: Let $G$ be a group, $g \in G$, $|g| = n < \infty$, and $m \in \mathbb{N}$. Then $|g^m| = \frac{n}{d}$ where $d =$ gcd$(m, n)$.
Proof: Write $n = db, m = dc$ for some $b, c \in \mathbb{N}$. First note that $(g^m)^b = g^{mb} = g^{dcb} = g^{nc} = (g^n)^c = 1$. Thus $|g^m|$ divides $b$. Let $|g^m| = k$. Then 
$(g^m)^k = 1 \Rightarrow g^{mk} = 1 \Rightarrow n|mk \Rightarrow b|ck$. Since $d =$ gcd$(m, n)$, gcd$(b, c) = 1$. Thus $b|k$ and $|g^m| = b$.
