Elements of a given order in a group

Let C=<x> be a cyclic group generated by the element x, with $\vert x\vert =n.$ Denote by $Gen(C)=\{y\in C:<y>=C\}$ the set of generators of C. It is easy to see that $y\in Gen(C)$ if and only if y=x^m, where m, $1\leq m\leq n,$ is a number relatively prime to n. If $E_n=\{m:1\leq m\leq n,(m,n)=1\},$ the mapping $m\rightarrow x^m$ is a bijection from E_n to Gen(C). The function $\phi :n\rightarrow$ $\vert E_n\vert$ is called the Euler phi function. Euler's function has two basic properties that are relatively easy to verify:

(a) For p^k a prime power, $\phi (p^k)=p^k(1-{ 1\over p}),$ and

(b) For m and n relatively prime, $\phi (mn)=\phi (m)\phi (n).$

Theorem (Frobenius) - Berliner Sitzungsberichte, 1895, p. 984

If n divides the order of a group, then the number of elements in the group whose orders divide n is a multiple of n.

Proof: Let G be a group of smallest order g for which the Theorem fails. By this assumption the Theorem is true for all groups H with $\vert H\vert <g.$ We call G a minimal counterexample. We proceed to contradict the minimality of G, and thus conclude that such G, in fact, does not exist.

For the group G, let n be the largest factor of g for which the Theorem fails. Since the Theorem is clearly true for n=1 and n=g, it follows that 1<n<g. Let N_m denote the number of elements in G whose order divides m. Furthermore, let p be a prime which divides g. We have

N_np=N_n+N_n^',

where N_n^' denotes the number of elements in G whose order divides np but not n. We aim to show that $n\vert N_n.$ Since by the inductive assumption $np\vert N_{np},$ and therefore $n\vert N_{np},$ we conclude the proof if we show that $n\vert N_n^{'};$ then n divides the difference N_np-N_n^'=N_n.

Let $A=\{x\in G:$ order of x divides np but does not divide $n\}$; $\vert A\vert =N_n^{'}.$ Write $n=p^{\lambda -1}s,$ with (p,s)=1, that is, p and s are relatively prime. Observe that if $x\in A,$ then $p^{\lambda}$ divides the order of x. To show that $n=p^{\lambda -1}s$ divides $\vert A\vert ,$ we first show that $p^{\lambda -1}$ divides $\vert A\vert ,$ then show that s divides $\vert A\vert .$ (Note also that if $\vert A\vert =0$ we are done.)

1. Let $y_1\in A,$ $\vert y_1\vert =p^{\lambda}t_1.$ Then all the $p^{\lambda -1}(p-1)\phi (t_1)$ generators of <y₁> are in A; denote this set by A₁. Select $y_2\in A\backslash A_1,$ $\vert y_2\vert =p^{\lambda}t_2.$ Again there are $p^{\lambda -1}(p-1)\phi (t_2)$ generators of <y₂>, all of them in A; call this set A₂. Note that $A_1\cap A_2=\emptyset$, for if $y\in A_1\cap A_2$ then <y₁>=<y>=<y₂>, a contradiction. Since A is finite we have $A=\bigcup A_i$ (disjoint union), and since $p^{\lambda -1}( p-1)$ divides A_i for all i, we conclude that $p^{\lambda -1}( p-1)$ divides $\vert A\vert ,$ and hence $p^{\lambda -1}$ divides $\vert A\vert .$

2. (a) If $x\in A,$ $\vert x\vert =p^{\lambda}t,$ then x can be written uniquely as x=yz, with y and z commuting and $\vert y\vert =p^{\lambda}$ and $\vert z\vert =t.$ Indeed, the cyclic group <x> can be written as a direct sum <x>=YZ, where Y is a subgroup of <x> of order $p^{\lambda}$ and Z is a subgroup of <x> of order t. Thus x=yz, with $y\in Y$ and $z\in Z$, as stated. Furthermore, since y and z are in <x>, they are both powers of x.

As to uniqueness, if x=yz, with y and z as above, then $x\in <y,z>.$ Since $\vert <y,z>\vert =p^{\lambda}t=\vert <x >\vert ,$ we conclude that <y,z>=<x>. Thus y and z are in <x> and uniqueness follows from the internal direct sum decomposition of <x>=<y><z>. We call y the p-constituent of x.

(b) For $y\in A$ with $\vert y\vert =p^{\lambda},$ let $C_ y=\{x\in A:y$ is the p-constituent of $x\}.$ Note that if y₁ and y₂ are two distinct elements of order $p^{\lambda}$ in A, then $C_{y_1}\cap C_{y_2}=\emptyset ;$ indeed, this follows from the uniqueness of the p-constituent established in (a) above. We can now conclude that the subsets C_y partition A.

(c) Let $y\in A,$ $\vert y\vert =p^{\lambda}.$ Denote by K_y the centralizer of y in G. Clearly $C_y\subseteq K_y.$ Let $r=\vert K_y/<y>\vert ,$ and let d=gcd(r,s), that is, d is the greatest common divisor of r and s. Since r<g, by the inductive assumption there exist a multiple of d, say cd, elements in K_y/<y> whose orders divide d. Let $\bar {z}$ be such a coset of <y> in K_y. We can represent $\bar {z}$ in the form z<y>, with $\vert z\vert =t,$ a divisor of d. [Indeed, $<y>=\bar {z}^t=z_1^t<y>$, and therefore z₁^t=yⁱ, for some i. We seek j such that z=z₁y^j satisfies 1=z^t=z₁^ty^jt=yⁱy^jt=y^i+jt. Since $(t ,p^{\lambda})=1,$ such a j exists; take j=-it^-1 (mod $p^{\lambda}).$] Then $zy\in C_y.$ Each element of K_y/<y> whose order divides d produces in this manner an element of C_y. Thus $\vert C_y\vert =cd.$

(d) Consider $\bigcup C_{y^w},$ the disjoint union taken over all the conjugates of y in G. We assert that s divides $\vert$ $\bigcup C_{ y^w}\vert .$ We have $\vert\bigcup C_{y^w}\vert =$ $\vert G:K_y\vert cd={g\over {p^{ \lambda}r}}cd$. Since g is divisible by s and r, it follows that gd is divisible by rs. Hence s is a divisor of ${{ gdc}\over r}.$ Since s and $p^{\lambda}$ are relatively prime, s must also be a factor of ${{gdc}\over {p^{\lambda}r}}=$$\vert$ $\bigcup C_{y^w}\vert$. In view of (b) above, this shows that s divides $\vert A\vert .$ This ends the proof.

By making use of the Möbius function we can obtain an expression for the number of elements whose order is exactly n in terms of the number of elements whose orders divide the divisors d of n. Specifically, denote by f(d) the number of elements whose orders are exactly n. Let h(d) denote the number of elements whose orders divide d. Clearly we have, $h(n)=\sum_{d\vert n}f(d).$ Möbius inversion now yields $f(n)=\sum_{d\vert n}h(d)\mu (d,n),$ where $\mu$ is defined to be 0, unless n/d is a product of k distinct primes, in which case it equals (-1)^k. Frobenius' Theorem informs us that h(d)=m is a multiple of d. We thus conclude as follows:

* If n divides the order of a group, then the number of elements of order exactly n is equal to $\sum_{d\vert n}(-1)^km_dd$. Here the sum is over only those divisors d of n with the property that n/d is a product of any number (k, say) of distinct primes. Furthermore, m is the number of elements whose orders divide d.