Fast way of calculating the order of an element in $\mathbb{Z}_n$?

Question

Is there a fast way of calculating the order of an element in $\mathbb{Z}_n$?

If i'm asked to calculate the order of $12 \in \mathbb{Z}_{22}$ I just sit there adding $12$ to itself and seeing if the sum is divisible by $22$. Is there an easier way?

Answer 1

The order of $12 \in \mathbb Z_{22}$ is given by:$$\frac{|\mathbb Z_{22}|}{\gcd(12, |\mathbb Z_{22}|)} = \dfrac {22}{2} = 11$$

In the general case, for $m \in \mathbb Z_n$, and $n = |\mathbb Z_n|$, we have that the order of $m$ is equal to: $$\frac n{\gcd(m,n)}$$

Answer 2

Hint $\ $ Note that $\ n\in \left<12\right> = 12k + 22\,\Bbb Z\iff n = 12k + 22j \!\overset{\rm Bezout\!}\iff \color{#c00}2=\gcd(12,22)\mid n$

Thus in $\,\Bbb Z_{22}\,$ we have $\left<12\right> = \left<\color{#c00}2\right>.\, $ But clearly $\left<2\right> =\{2\cdot 1,\, 2\cdot 2,\ldots, 2\cdot\color{#0a0}6\}\,$ has order $\,\color{#0a0}6$.

The same works generally: $ $ in $\,\Bbb Z_m,\,$ $\,\left<k\right> = \left<\gcd(k,m)\right>\,$ so has order $\ m/\gcd(k,m)$