Cardinality of the set of elements of fixed order.

Question

Let us consider the group $G:=\mathbb{Z}_N^a$ (the product of the cyclic group with $N$ elements with itself $a$ times). Suppose we are given a number $m$ that divides $N$.

I would like to know how many elements $x$ in $G$ have the property that $(N/m)x$ has order precisely $m$ (and not any number dividing $m$).

For example, if $a$ equals $1$, and $m=p^{\alpha}$ for $p$ a prime, the number of such elements is $N-N/p$, if $m= p^{\alpha} q^{\beta}$, it is $N-N/p-N/q+N/pq$.

I expect that in general there might be a closed formula for this number, perhaps involving the Euler function $\phi$. Can anyone produce it or give me a suggestion on a good reference where I could look for it?

Answer 1

Let $Ord(m)$ be the number of elements of order $m$ in $\mathbb{Z}_N^a$, where $m|N$. A nice way to compute $Ord(m)$ is to start from the observation

$$\sum_{m|N} Ord(m) = N^a$$

and to apply Möbius inversion:

$$Ord(m) = \sum_{d|m} \mu(m/d)d^a.$$

$Ord(m)$ is multiplicative (if $m$ and $n$ are relatively prime, then $Ord(mn) = Ord(m)Ord(n)$; cf. Chinese remainder theorem). Thus, it is not hard to work out $Ord(m)$ in terms of how $\mu$ behaves on the prime-power factors of $m$. After a little algebra,

$$Ord(m) = m^a \prod_{\text{prime } p|m} (1-\frac1{p^a}).$$

Notice that $N$ has receded from the picture. Indeed, for $m|N$, let

$$\mathbb{Z}_m^a \hookrightarrow \mathbb{Z}_N^a$$

be the obvious inclusion of abelian groups, mapping onto the subgroup of elements whose order divides $m$. Then the set of elements of order exactly $m$ in $\mathbb{Z}_m^a$ maps onto the set of elements of order exactly $m$ in $\mathbb{Z}_N^a$, so we are just counting the former set.

Edit: Oh wait, I didn't quite answer your exact question, did I? But no problem: the number of $x$ such that $(N/m)x$ has order exactly $m$ is just the inverse image of the set of order $m$ elements w.r.t. the map

$$(N/m) \cdot -: \mathbb{Z}_N^a \to \mathbb{Z}_N^a.$$

This map has kernel of size $(N/m)^a$, and the inverse image we want consists of $Ord(m)$ many distinct cosets of this kernel. Thus, the answer to the actual question is

$$N^a \prod_{\text{prime } p|m} (1 - \frac1{p^a}).$$