Home

> urticator.net
Search

About This Site
> Domains
Glue
Stories

Computers
Driving
Games
Humor
Law
> Math
Numbers
Science

Game Theory Section
> A Theorem on Finite Abelian Groups
Probability
Miscellaneous

 > The Structure of Un
The Proof
An Example

## The Structure of Un

prev

The main thing to observe about the groups Un 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 m1m2, where m1 and m2 are relatively prime. It then so happens that if we know all about congruence mod m1 and m2, 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 m1 and m2,

a ≡ b mod m1
a ≡ b mod m2.

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

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

o(Upk) = (1 - 1/p) × pk = (p-1) pk-1.

As for the internal structure of Upk, 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 Z2 falls out. The whole group has order 2k-1—i.e., that many elements—so what's left after removal of the factor Z2 is a cyclic group of order 2k-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 Z2.

That's everything I wanted to say about the groups Un. However, there is one related point I'd like to make, which is that the cyclic groups Zn can be decomposed into prime power factors, too. In fact, the decomposition follows from the same congruence argument as above, because any group Zn 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 U133 was the same as the cyclic group Z12 × 132, but now we can further decompose the cyclic group into prime powers, like so.

U133 = Z12 × 132 = Z22 × Z3 × Z132

next

See Also

Complementary Parts
Example, An (A Theorem on Finite Abelian Groups)
Exceptions Explained, The
Multiplication in Base 10
Multiplication in Base 7
Other Bases
Proof, The
Repeat Length
Theorem on Finite Abelian Groups, A
Usual Random Thoughts, The

@ May (2001)