Possible periods of the elements in $\mathbb{Z}_n$ I'm looking into different order finding algorithms, and something i often notice is that a specific order happens more often than other orders for elements 
in the multiplicative group $\mathbb{Z}_n^*$.
For example in $\mathbb{Z}_{77}^*$. The order is often 30. I found this by the following elements: 8,9,10,12,18...
And this are just the ones i checked.
Is there some theorem about which orders are possible in a certain group $\mathbb{Z}_n^*$? Or how much each order occurs?
 A: The simplest answer is when $n=p$, a prime.
Then the multiplicative group $\mathbb{Z}_p^*$ is cyclic of order $p-1$ and so the orders that occur are exactly the divisors of $p-1$. Moreover, if $d$ divides $p-1$, then there are exactly $\phi(d)$ elements of order $d$ in $\mathbb{Z}_p^*$.
Now take $n=pq$, where $p$ and $q$ are primes.
Then $\mathbb{Z}_{pq}^* \cong \mathbb{Z}_p^* \times \mathbb{Z}_q^*$. The order of $(a,b)$ is $lcm(o(a),o(b))$. The exact number of elements of a given order is not so easy to see in this representation, but it can be done with some work. 
To take your example, with $n=77=7\cdot11$, we get this table of orders of elements of $\mathbb{Z}_{77}^*$:
$$
\begin{matrix}
& & & o(b) \\
o(a) & 1 & 2 & 5 & 10 \\
1 & 1 & 2 & 5 & 10 \\
2 & 2 & 2 & 10 & 10 \\
3 & 3 & 6 & 15 & 30 \\
6 & 6 & 6 & 30 & 30 \\
\end{matrix}
$$
Complement this table with how many elements $a\in\mathbb{Z}_{7}^*$ and $b\in\mathbb{Z}_{11}^*$ exist of each possible order, and you get the same for $\mathbb{Z}_{77}^*$.
The general case is analogous but of course more complicated. First, decompose $\mathbb{Z}_n^*$ as a product of $\mathbb{Z}_{p^e}^*$ for each prime power that appears in the factorization of $n$. Then $\mathbb{Z}_{p^e}^*$ is cyclic and you can proceed as above.
