# Order of an element in a group

Explain why external direct products $\mathbb{Z}_8 \times \mathbb{Z}_4$ and $\mathbb{Z}_{80000000}\times \mathbb{Z}_{4000000}$ have same number of elements of order 4

I am thinking as for every divisor $d$ of the order of the group, there are $\phi(d)$ (Euler's $\phi$) elements of order $d$, in both the external direct products the number of elements of order $4$ are the same. Please suggest if this logic is ok.

-
All caps is interpreted as shouting. Please don't use them. –  Arturo Magidin Aug 18 '11 at 18:17
It is false in general that the number of elements of order $d$ is a group is $\phi(d)$ when $d$ divides the order (even in the abelian case). For example, in $\mathbb{Z}_2\times\mathbb{Z}_2$, there are zero elements of order $4$, even though $4$ divides the order. So that argument is false. On the other hand, you might want to consider the number of elements of order $k$ in a cyclic group, and then figure out when an element $(a,b)$ of $A\times B$ will be have order $k$ in terms of the orders of $a$ and of $b$. –  Arturo Magidin Aug 18 '11 at 18:21
The "OK" part was not the problem; it was the title of your post which was just a big yell. Of course acronyms (such as "UFD") can be in all caps. –  Arturo Magidin Aug 18 '11 at 18:25
Thanks, I get your point. Can I say that there are phi (4) elements of order 4 in each of the cyclic groups z4 , z8000000 and z4000000 and consequently, then analyze the orders of the elements in two external direct products, which I think is going to come out same. –  Tav Aug 18 '11 at 18:27
have you proven that the number of elements of order $d$ in $\mathbb{Z}_n$ is $\phi(d)$ when $d|n$? If you have, then yes (being suitably careful in that analysis, of course); if not, you'll want to prove that first. –  Arturo Magidin Aug 18 '11 at 18:32

First:

Lemma 1. Let $A$ and $B$ be groups. An element $(a,b)\in A\times B$ has order $n$ if and only if $\mathrm{lcm}(\mathrm{order}(a),\mathrm{order}(b)) = n$.

Proof. If $(a,b)$ has exponent $n$, then $(1,1) = (a,b)^n = (a^n,b^n)$, so $a^n=1$, $b^n=1$, hence $\mathrm{order}(a)|n$ and $\mathrm{order}(b)|n$. Thus, $\mathrm{lcm}(\mathrm{order}(a),\mathrm{order}(b))|n$. So the order of $(a,b)$ is a multiple of $\mathrm{lcm}(\mathrm{order}(a),\mathrm{order}(b))$.

Conversely, if $k=\mathrm{lcm}(\mathrm{order}(a),\mathrm{order}(b))$, then $a^k=1$ and $b^k=1$ (since $k$ is a multiple of the orders), so $(a,b)^k = (1,1)$. Thus, the order of $(a,b)$ divides $\mathrm{lcm}(\mathrm{order}(a),\mathrm{order}(b))$. QED

Lemma 2. Let $G$ be a group, and let $g\in G$. If the order of $g$ is $n$ ($n=0$ if $g$ is of infinite order), and $k\gt 0$, then the order of $g^k$ is $n/\gcd(n,k)$.

Proof. Let $\gcd(n,k)=d$, and write $n=dm$, $k=d\ell$, $\gcd(m,\ell)=1$. Then $n/\gcd(n,k)=m$. Since $(g^k)^m = g^{km}$, and $km=d\ell m = n\ell$, then $(g^k)^m = (g^n)^{\ell} = 1$. So the order of $g^k$ divides $n/\gcd(n,k)$. On the other hand, if $(g^{k})^a = 1$, then $n|ka$, hence dm|d\ell a$, hence$m|\ell a$. Since$\gcd(m,\ell)=1$, it follows that$m|a$, so$n/\gcd(n,k)|a$. Thus, the order of$g^k$is a multiple of$n/\gcd(n,k)$. QED Corollary. If$G$is a cyclic group of order$n\gt 0$, then the number of elements of order$d$in$G$is$0$if$d$does not divide$n$, and$\varphi(d)$(Euler's$\varphi$) if$d|n$. Proof. Let$x$be a generator of$G$. If$d$doesn't divide$n$, then no element can have order$d$and we are done. Suppose then that$d$divides$n$. Then$n=dk$. By Lemma 2, an element$x^a\in G$has order$d$if and only if$d=n/\gcd(a,n)$, if and only if$\gcd(a,n)=k$. Thus the question reduces to asking how many$a$,$0\leq a\lt n$, satisfy$\gcd(a,n)=d$. Such an$a$must be of the form$a=dm$with$0\leq m\lt n/d = k$, and$\gcd(m,n/d)=\gcd(m,k)=1$. Thus, the number is precisely$\varphi(k)$, the number of nonnegative integers smaller than$k$and relatively prime to$k$. QED Now, consider the case of$A\times B$and elements of order$4$.$(a,b)\in A\times B$has order$4$if and only if the lowest common multiple of the orders of$a$and$b$is$4$, if and only if: •$a$and$b$both have order$4$; or •$a$has order$2$and$b$has order$4$; or •$a$has order$4$and$b$has order$2$; or •$a$has order$1$and$b$has order$4$; or •$a$has order$4$and$b$has order$1$. That is, one entry has order$4$, and the other entry has exponent$4$. In both your cases, since$4$divides the order of each of the two factors (in both products), you have$\varphi(4)$elements of order$4$in each factor group, and$\varphi(4)+\varphi(2)+\varphi(1)$elements of exponent$4$in each factor group. So the counts for elements of order$4$in the products are the same:$2\varphi(4)(\varphi(4)+\varphi(2)+\varphi(1)) - \varphi(4)^2$. (If you want$a$to have order$4$, you have$\varphi(4)$ways of choosing$a$; then you have$\varphi(4)+\varphi(2)+\varphi(1)$ways of choosing$b$of exponent$4$. The same analysis holds if you first decide that$b$has order$4$instead and$a$has exponent$4$. However, this counts the case in which both$a$and$b$have order$4$twice, which occurs in$\varphi(4)\times\varphi(4)\$ ways, so we subtract it once to get the inclusion-exclusion count right.)

-
Thank you so much for detailed and informative reply. You are the best teacher that a student can have. –  Tav Aug 20 '11 at 19:13