# How many elements of order d?

My instructor has given this question as an exercise: Let $G=\mathbb{Z}_n\times \mathbb{Z}_m$ and $d=p^k$ for some prime $p$ such that $d$ divides both $n$ and $m$. How many elements of order $d$ does $G$ have?

I'll write my attempt for solution down and I actually have found an answer yet it seems a little unusual so I could not be sure about my solution, can you please check it out and correct me? Thank you.

Solution:

$$\forall(a,b) \in \mathbb{Z}_n\times \mathbb{Z}_m,\quad|(a,b)|=\operatorname{lcm}(|a|,|b|)$$ For the elements of order $d$, either $|a|$ or $|b|$ is $d$ or both are $d$. Since $d$ both divides $n$ and $m$, the power of $p$ up to $k$ divide $n$ and $m$ as well.

First fix $|a|=d$, then the possibilities for $|b|$ are $1,p,p^2,....,p^k$. In $\mathbb{Z}_n$ the number of elements of order $n$ is $\phi(n)$ which is the Euler Phi Function.

Therefore, the number of elements of order $d$ in the form of $(a,b)$ such that $|a|=d$ and $|b|=1,p,p^2,....,p^k$:

$$\phi(d)[1+\phi(p)+\phi(p^2)+ \dots+ \phi(p^k)]$$

The relations $\phi(p)=p-1$ and $\phi(p^n)= p^n-p^{n-1}$ make the above equation as follows:

$$\phi(d)[1+ p-1+p^2-p+ \dots + p^k-p^{k-1}]=d \phi(d)$$

So fixing $|b|=d$ will yield the same result. However, I've considered the case of both $|a|$ and $|b|$ are $d$ two times so I need to subtract $\phi(d)\phi(d)$.

To sum up, I've found: $2d\phi(d)-\phi(d)\phi(d)$.

-
Rats, it looks fine...and surprising! I never thought of this this way...nice! +1 , even if it happens to be the calculation is wrong, for the nice self work presented. – DonAntonio Jan 5 '13 at 1:01
@DonAntonio thank you for your feedback! Can you mention me the way you thought to find the answer, I'm interested in different solution – Ada Jan 5 '13 at 10:20