Cardinality of the set of elements of fixed order. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T03:05:36Z http://mathoverflow.net/feeds/question/79166 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79166/cardinality-of-the-set-of-elements-of-fixed-order Cardinality of the set of elements of fixed order. Math 2011-10-26T14:51:59Z 2011-10-26T19:47:52Z <p>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$.</p> <p>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$).</p> <p>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$.</p> <p>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?</p> http://mathoverflow.net/questions/79166/cardinality-of-the-set-of-elements-of-fixed-order/79171#79171 Answer by Todd Trimble for Cardinality of the set of elements of fixed order. Todd Trimble 2011-10-26T16:17:32Z 2011-10-26T19:47:52Z <p>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 </p> <p>$$\sum_{m|N} Ord(m) = N^a$$ </p> <p>and to apply <a href="http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula" rel="nofollow">M&ouml;bius inversion</a>: </p> <p>$$Ord(m) = \sum_{d|m} \mu(m/d)d^a.$$ </p> <p>$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, </p> <p>$$Ord(m) = m^a \prod_{\text{prime } p|m} (1-\frac1{p^a}).$$ </p> <p>Notice that $N$ has receded from the picture. Indeed, for $m|N$, let </p> <p>$$\mathbb{Z}_m^a \hookrightarrow \mathbb{Z}_N^a$$ </p> <p>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. </p> <p><b>Edit:</b> 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 </p> <p>$$(N/m) \cdot -: \mathbb{Z}_N^a \to \mathbb{Z}_N^a.$$ </p> <p>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 </p> <p>$$N^a \prod_{\text{prime } p|m} (1 - \frac1{p^a}).$$ </p>