# Number of reduced residue classes with given order?

In general, is there a way to compute the number of reduced residue classes $$\pmod n$$ of a certain order?

For example, say $$n=385=5\times7\times11$$. Then $$(\mathbb Z/385\mathbb Z)^\times\cong(\mathbb Z/5\mathbb Z)^\times\times (\mathbb Z/7\mathbb Z)^\times\times (\mathbb Z/11\mathbb Z)^\times.$$ In $$(\mathbb Z/5\mathbb Z)^\times$$ there are $$1,1,2$$ elements of orders $$1,2,4$$.

In $$(\mathbb Z/7\mathbb Z)^\times$$ there are $$1,1,2,2$$ elements of orders $$1,2,3,6$$.

In $$(\mathbb Z/11\mathbb Z)^\times$$ there are $$1,1,4,4$$ elements of orders $$1,2,5,10$$.

Then, if I wanted to see how many elements of order $$4$$ (say) there were in $$(\mathbb Z/385\mathbb Z)^\times$$, I can 'brute' force and check all the triples $$(a\pmod5,b\pmod7,c\pmod{11})$$ for which $$\text{lcm}(\text{ord}_5a,\text{ord}_7b,\text{ord}_{11}c)=4$$ and conclude that there are $$8$$ elements of order $$4$$.

Is there a faster method/theorem to compute this? And if there isn't, what about for $$\lambda(385)=60$$, the maximum order? Is there a way to compute how many elements there are of order $$60$$?

I am not entirely sure about the first part. The "nice" thing is that you can just focus on the orders and then calculate how many elements of a given order there are. Since the group of units mod $$p$$ is cyclic, the number of elements of order $$n$$ is equal to the number of solutions of the equation

$$kn \equiv 0 \pmod{p-1}$$

such that $$k m \neq 0 \pmod{p-1}$$ for any $$m < n$$.

For the last part, note that you want to calculate the number of generators for each prime. The number of generators $$\mod p$$ is equal to $$\phi (\phi(p)) = \phi(p-1)$$. Hence, if $$n$$ is a square-free product of primes then

$$\lambda (n) = \prod _{p \mid n} \phi(p-1)$$

Note the square-free condition ensures that the $$\mod p$$ groups are cyclic. Otherwise, it gets a bit messy and I haven't given it much thought.

Actually, it is well known that if $$n=\prod_{i=1}^{t}p_i^{\alpha_i}$$ ,

then $$\phi(n)=n\prod_{i=1}^{t}(1-\frac{1}{p_i})$$