2
$\begingroup$

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.

  • 2
    All caps is interpreted as shouting. Please don't use them.2011-08-18
  • 0
    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$.2011-08-18
  • 1
    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.2011-08-18
  • 0
    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.2011-08-18
  • 0
    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.2011-08-18
  • 0
    @arturo magidin: Yes, I think I can use this result here. So could you please, explain it to me, why this is happening. Is the order equivalence true only because the number elements of each order in a cyclic group depends only on phi (d), only care required is that d should be a divisor of order of the group in each case.2011-08-18
  • 0
    Explain why *what* is happening? Why the number of solutions in a cyclic group is $\varphi(d)$ when $d$ divides the order of the group? Why the two groups have the same number of elements of order $4$?2011-08-18
  • 0
    Sorry for being so vague. Why two groups have same number of elements of order 4 ?2011-08-18

1 Answers 1

4

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

  • 2
    Thank you so much for detailed and informative reply. You are the best teacher that a student can have.2011-08-20