Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to tell if U(n) is cyclic?

  1. Feb 29, 2012 #1
    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. jcsd
  3. Feb 29, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    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
  4. Mar 1, 2012 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook