# How to tell if U(n) is cyclic?

1. Feb 29, 2012

### iceblits

In my book U(n) is defined as all numbers less than n that are relatively prime to n. U(n) is cyclic for some n but not for all. I was wondering if there is theory behind how to tell if U(n) will be cyclic or, even better, what elements of U(n) generate U(n). Also, the formal name of this group would help a lot too, if anyone knows what it is...

2. Feb 29, 2012

### morphism

This is the group of units mod n (i.e. the group of units in the ring Z/nZ). Its isomorphism type is fully known. First note that if $n=p_1^{a_1} \cdots p_r^{a_r}$ is the prime factorization of n then $$U(n) = U(p_1^{a_1}) \times \cdots \times U(p_r^{a_r})$$ by the Chinese remainder theorem. Thus it suffices to determine what $U(p^a)$ looks like for a prime p. Here there are two cases to consider.
1) If p is odd then $U(p^a)$ is cyclic (of order $\varphi(p^a)$).
2) If p=2 then $U(2)$ is trivial (hence cyclic) but for a>1 $U(2^a) = \mathbb Z / 2\mathbb Z \times \mathbb Z/2^{a-2} \mathbb Z$ (which is noncyclic if a>2).
In particular, it follows that U(n) is cyclic iff n=2, 4, p^a or 2p^a, where p is an odd prime.

Depending on how much group theory you know, these results might not be so easy to prove. They follow most easily from the structure theorem for finitely generated abelian groups, which is a nontrivial theorem.

When $U(n)$ is cyclic, a generator is called a primitive root mod n. In general finding a primitive root explicitly isn't an easy task.

Last edited by a moderator: Mar 1, 2012
3. Mar 1, 2012

### iceblits

Ahh I'm not familiar with alot of this notation (I'm still in an introductory Abstract Algebra class), and I'm also not familiar with the Chinese remainder theorem (although I'm searching it up right now). However, you are saying that if I can write n as 2,4, or p^a or 2p^a where a is any natural number?
Also, thanks for providing the group name...it will help me alot.