MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Questions suitable for intro group theory homework assignments are not suitable for MO. Please see the faq. Voting to close. – Gerry Myerson Oct 26 '11 at 21:26
up vote 7 down vote accepted

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

share|cite|improve this answer
Thank you very much! Your explanation is very clear and neat. – Math Oct 27 '11 at 12:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.