Count elements with a given order in the multiplicative group $n=pq$ (RSA)
It's not hard to compute, the number of elements with order precisely $r$ is:
$$F_{p-1, q-1}( \phi(r))$$
where $F$ is this function:
If the prime factorization of $r = r_1^{e_1} r_2^{e_2} ... r_n^{e_n}$ then
$$F_{p-1, q-1}(r) = F_{p-1, q-1}(r_1^{e_1}) \cdot F_{p-1, q-1}(r_2^{e_2}) \cdot ... \cdot F_{p-1, q-1}(r_n^{e_n})$$
If $s$ is prime and $e&gt;0$, then $F_{p-1, q-1}(s^e)$ depends on $\gcd( s^e, p-1) = s^a$ and $\gcd( s^e, q-1) = s^b$
If $a, b &lt; e$, then $F_{p-1, q-1}(s^e) = 0$ (i.e. there are no elements with that order)
If $a=e, b &lt; e$, then $F_{p-1, q-1}(s^e) = s^b$
If $b=e, a&lt; e$, then $F_{p-1, q-1}(s^e) = s^a$
If $a=b=e$, then $F_{p-1, q-1}(s^e) = s^e + s^{e-1}$
This allows us to compute the number of elements in all cases.