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?



Cardinality of the set of elements of fixed order.
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](http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula): 


$$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}).$$ 


