La respuesta más sencilla es cuando $n=p$ un primo.
Entonces el grupo multiplicativo $\mathbb{Z}_p^*$ es cíclico de orden $p-1$ y así los órdenes que se producen son exactamente los divisores de $p-1$ . Además, si $d$ divide $p-1$ entonces hay exactamente $\phi(d)$ elementos de orden $d$ en $\mathbb{Z}_p^*$ .
Ahora toma $n=pq$ , donde $p$ y $q$ son primos.
Entonces $\mathbb{Z}_{pq}^* \cong \mathbb{Z}_p^* \times \mathbb{Z}_q^*$ . El orden de $(a,b)$ es $lcm(o(a),o(b))$ . El número exacto de elementos de un orden determinado no es tan fácil de ver en esta representación, pero se puede hacer con algo de trabajo.
Para tomar su ejemplo, con $n=77=7\cdot11$ obtenemos esta tabla de órdenes de elementos de $\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} $$ Completa esta tabla con cuántos elementos $a\in\mathbb{Z}_{7}^*$ y $b\in\mathbb{Z}_{11}^*$ existen de cada orden posible, y se obtiene lo mismo para $\mathbb{Z}_{77}^*$ .
El caso general es análogo pero, por supuesto, más complicado. En primer lugar, hay que descomponer $\mathbb{Z}_n^*$ como producto de $\mathbb{Z}_{p^e}^*$ para cada potencia prima que aparece en la factorización de $n$ . Entonces $\mathbb{Z}_{p^e}^*$ es cíclico y se puede proceder como en el caso anterior.