Count elements with a given order in the multiplicative group $n=pq$ (RSA) We know that the order of an element $a$ in the group $\mathbb Z_n^*$ is $k$ where $k|lcm(p-1,q-1)$ where p,q are distinct primes.

Something else i think we know is that the elements that have order $lcm(p-1,q-1)$ will generate exactly $\frac{φ(n)}{lcm(p-1,q-1)}$ different subgroups which may have common elements (in order to jointly generate all the elements of the group). Based on that, if the n was prime, we could easily count the elements of each order by doing $φ(order)$. (if it is prime, one element could generate all the others)

Is it possible to count how many elements have a given order?

For example: $n=5*7$

How many elements have order 6? (I know it's 6, but is there a generic way to find it?)

CRT could give an approximation in this case but you should still filter out the elements that may have smaller order that divides in this case 6 (1,2,3).

Here are the subgroups with order 12:

2,4,8,16,32,29,23,11,22,9,18,1
3,9,27,11,33,29,17,16,13,4,12,1
12,4,13,16,17,29,33,11,27,9,3,1
17,9,13,11,12,29,3,16,27,4,33,1
18,9,22,11,23,29,32,16,8,4,2,1
23,4,22,16,18,29,2,11,8,9,32,1
32,9,8,11,2,29,18,16,22,4,23,1
33,4,27,16,3,29,12,11,13,9,17,1


One interesting detail is that the generators for each group are present to exactly three other subgroups. For example, 33 is inside 3,12,17 subgroups. (each contains the other elements in positions m where $gcd(m, 12)=1$ so we have 4 permutations of each of the two subgroups)

With order 6:

4,16,29,11,9,1
9,11,29,16,4,1
19,11(-24),34,16,24,1
24,16(-19),34,11,19,1
26(-9),11,6,16,31,1
31(-4),16,6,11,26,1


Here, each generator is present in another subgroup

EDIT:

My second theorem seems to be little flawed:
I assumed that combining all the subgroups of order $lcm(p-1,q-1)$ would generate all the elements of the multiplicative group n. But as we can see from my example, they do not since they don't generate the elements 6,19,24,26,31,34.



Here are some good resources that could be useful mult. groups mod n and carmichael function.
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.