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)