Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
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. –  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
show 3 more comments

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

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.