# How to determine if $G$ contains an element of order $k$?

I'm struggling with this kind of problem:

Given a group $G= (\mathbb{Z}/n\mathbb{Z})^*$ (which is the multiplicative modulo group), determine if the group contains an element of order $k$. What is the general strategy here?

For example, given a group $G=(\mathbb{Z}/3700\mathbb{Z})^*$,

Does $G$ have an element of order $5$? of order $37$? of order $8$ ?

The only things I can think of are $\#G = 2^2 \cdot 5^2 \cdot 37$, and Euler's $$\phi(n)= n \prod_{p|n}(1-1/p)$$

I don't need exact answers (well you can give it), but rather strategies to solve these exercises.

First, note that it's enough to be able to solve this problem when $k$ is a prime or a power of a prime. That's because, if $k_1$ and $k_2$ are relatively prime, then an abelian group $G$ contains elements of order $k_1$ and $k_2$ if and only if it contains an element of order $k_1k_2$. (That assertion is a good exercise on its own.)
Second, for this specific problem it's crucial to be able to write the isomorphism class of $(\mathbb Z/n\mathbb Z)^*$ in some standard form for finite abelian groups. For example, \begin{align*} (\mathbb Z/3700\mathbb Z)^* &\cong (\mathbb Z/2^2\mathbb Z)^* \times (\mathbb Z/5^2\mathbb Z)^* \times (\mathbb Z/37\mathbb Z)^* \\ &\cong \mathbb Z/2\mathbb Z \oplus \mathbb Z/20\mathbb Z \oplus \mathbb Z/36\mathbb Z \\ &\cong \mathbb Z/2\mathbb Z \oplus \mathbb Z/4\mathbb Z \oplus \mathbb Z/5\mathbb Z \oplus \mathbb Z/4\mathbb Z \oplus \mathbb Z/9\mathbb Z \\ &\cong \mathbb Z/2\mathbb Z \oplus \mathbb Z/4\mathbb Z \oplus \mathbb Z/180\mathbb Z. \end{align*} The first isomorphism here is by the Chinese remainder theorem. The second isomorphism has to do with odd prime powers having primitive roots, so that these multiplicative groups are cyclic. The third and fourth isomorphisms are again the Chinese remainder theorem; the third line is a standard representation as the direct sum of cyclic groups of prime power order, while the fourth line is a standard representation in terms of invariant factors. (I'm using $\times$ and $\oplus$ interchangeably here ... in the first line the group operation is multiplication, while in subsequent lines the group operation is addition.)
• Can you maybe elaborate the last isomorphism? Is it because we already have $Z/4, Z/5$ in the product? I am not 100% sure I get that last part Jun 19 '13 at 19:15
• The last isomorphism is true because $\mathbb Z/5\mathbb Z \oplus \mathbb Z/4\mathbb Z \oplus \mathbb Z/9\mathbb Z \cong \mathbb Z/(5\cdot 4\cdot9)\mathbb Z$; that's the Chinese remainder theorem (4, 5, and 9 are pairwise relatively prime). It's useful because the last line is in the standard "invariant factors" form. There are probably some helpful exercises you can find about converting finite abelian groups back and forth between those two standard forms. Jun 19 '13 at 21:43