The Structure of U_n

The main thing to observe about the groups U_n is that they can be decomposed into prime power factors. Here's how that works … it all follows from one little fact. Suppose we can write n as a product m₁m₂, where m₁ and m₂ are relatively prime. It then so happens that if we know all about congruence mod m₁ and m₂, we also know all about congruence mod n. In other words, two numbers a and b are congruent mod n,

a ≡ b mod n,

if and only if they're congruent mod m₁ and m₂,

a ≡ b mod m₁
a ≡ b mod m₂.

Applying the rule repeatedly, we can break any group U_n into a product of groups of the form U_p^k, where p is a prime and k is a positive integer.

Now we just need to know what the groups U_p^k look like. First, let's see how many elements they have. The elements, remember, are the numbers relatively prime to p^k, mod p^k. Now, being relatively prime to a number of the form p^k is the same as not being divisible by p; so to get the elements of the group, we just remove every p^th number from the p^k distinct numbers mod p^k:

o(U_p^k) = (1 − 1/p) × p^k = (p−1) p^k−1.

As for the internal structure of U_p^k, well, I'll just summarize the results I found in Introduction to Number Theory.

• If p ≠ 2, then the group is cyclic, i.e., generated by a single element.
• If p = 2, then the group is cyclic except that a factor of the two-element cyclic group Z₂ falls out. The whole group has order 2^k−1—i.e., that many elements—so what's left after removal of the factor Z₂ is a cyclic group of order 2^k−2.

  There are a couple of special cases, of course. If k = 1, the whole group has only a single element; and if k = 2, the whole group has only two elements, and so is just the cyclic group Z₂.

That's everything I wanted to say about the groups U_n. However, there is one related point I'd like to make, which is that the cyclic groups Z_n can be decomposed into prime power factors, too. In fact, the decomposition follows from the same congruence argument as above, because any group Z_n can be thought of as a group of integers mod n, only under addition rather than multiplication. (Of course, the elements are no longer required to be relatively prime to n.)

For example, we knew from the discussion above that the group U_13³ was the same as the cyclic group Z_{12 × 13²}, but now we can further decompose the cyclic group into prime powers, like so.

U_13³ = Z_{12 × 13²} = Z_2² × Z₃ × Z_13²