Counting the number of elements of a particular order in $\mathbb{Z}_n$

Question

I am trying to count the number of elements of say order $10$ in $\mathbb{Z}_n$ for large $n$ say $n=10000$?

I know that the order of any element $[a]\in \mathbb{Z}_n$ is $\frac{n}{\gcd(a,n)}$. If $n$ is small, say $n=30$, then I can find all such $a$ by manually looking at all $a$ s.t. $$\frac{30}{\gcd(a,30)}=10$$ and find $a\in\{3,9,21,27\}$. But I'm not sure how to count for large $n$?

Answer 1

$\mathbb{Z}_n$ has this nice property that for $m|n$ there is precisely one subgroup $H\subseteq \mathbb{Z}_n$ of order $m$. And so any element of order $m$ has to belong to that subgroup $H$.

This means that regardless of what $n$ is, $g\in\mathbb{Z}_n$ is of order $m$ if and only if $m$ divides $n$ and $g$ is a generator of the unique subgroup $H$ of order $m$. This unique subgroup is obviously isomorphic to $\mathbb{Z}_m$. So all we need to do is to count generators of $\mathbb{Z}_m$. For that we use Euler's totient function $\varphi$. Thus we have:

The number of elements of order $m$ in $\mathbb{Z}_n$ is equal to $0$ if $m$ does not divide $n$ and $\varphi(m)$ otherwise.

Explicitly finding all of them is also not that hard, assuming $m$ is small enough. The unique subgroup $H$ is generated by $n/m$. Then every generator of $H$ is of the form $kn/m$ for $1\leq k<m$ relatively prime to $m$. So all we have to do is to find all numbers smaller than $m$ and relatively prime to it. For small enough $m$ (like $m=10$ in your case) this is very simple, you can just brute force all possibilities. However for big $m$ this is a very hard problem, I think at least as hard as integer factorization.

---

In your particular case $m=10$ and we get that there are $\varphi(10)=4$ elements of order $10$ in $\mathbb{Z}_{10000}$. Note that as long as $10$ divides $n$, $\mathbb{Z}_n$ will always have exactly $4$ elements of order $10$.

Now $n/m=1000$ in this case. Furthermore here is the list of all numbers relatively prime to $10$: $1,3,7,9$. Thus here is the list of all elements of order $10$ in $\mathbb{Z}_{10000}$:

$$\{1000, 3000, 7000, 9000\}$$

This also works well in your example where $n=30$. In this case $n/m=3$, the list of all numbers relatively prime to $10$ is the same, and the final list of generators is $\{3,9,21,27\}$. Exactly what you've said yourself.

Answer 2

Just you need to compute $\phi(n) $. And $\phi(n) $ means those numbers which are less than and prime to $n$. For example:- take $n$=$10$ then $\phi(10) $=$4$.