Home

> urticator.net
Search

> 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

## An Example

prev

For my example, I'll find the smallest group Un that contains the group G = ( Z9 )3—that is, three factors Zpk with p = 3 and k = 2.

We can obtain one factor by taking q = p and m = k+1, so that qm = 27; for the other factors, we need primes q of the form 9j+1, of which the first two are 19 and 37. Thus, we have

n = 19 × 27 × 37 = 19 × 999 = 18981.

Since that, by itself, doesn't make a very satisfying example, let me also find generators for the three factors Z9.

How does one do that? Well, the place to start is in the component groups U19, U27, and U37. The group U19, for example, is a cyclic group with 18 elements. The number 2 happens to be a generator, as one can see by computing successive powers mod 19.

1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1

We don't want a generator of the whole cyclic group Z18, though, just a generator of the factor Z9 … and for that we can use 22 = 4, since that generates only the even powers of two.

Now that we've found a generator for Z9 in the component group U19, the next step is to locate a copy of U19 inside the main group U18981 and find the corresponding generator within the copy. But that's easy enough! For any groups A and B, the product A × B contains a natural copy of A, namely, all the elements of the form (a,eB), where eB is the identity element of B. So, what we're looking for is a number x that's a generator mod 19, but an identity element mod 27 and 37 … in other words,

x ≡ 4 mod 19
x ≡ 1 mod 27
x ≡ 1 mod 37.

I claimed, back in The Structure of Un, that if we knew all about congruence mod relatively prime factors, we knew all about congruence mod the product, but I didn't give any details. How, then, do we find x?

Let me generalize a little. Suppose we're trying to solve a set of congruences

x ≡ ai mod mi,

where the factors mi are relatively prime. If we can find a set of numbers Gi that satisfy

Gi ≡ delta(i,j) mod mj,

then the solution x can be obtained by adding up appropriate multiples.

x = sum ( ai Gi )

(I don't know an official name for the numbers Gi, so I used the letter “G” because they remind me of Green's functions.)

It turns out, fortunately, that the numbers Gi are quite easy to determine. The number G corresponding to the factor 19, for example, needs to satisfy the equations

G ≡ 1 mod 19
G ≡ 0 mod 27
G ≡ 0 mod 37.

In other words, G needs to be a multiple of 27 × 37 = 999. Now, 999 is congruent to 11 mod 19; consulting the table of powers of two, above, we see that 11 ≡ 212, so that the inverse is 26 ≡ 7; and that gives us our number.

6993 = 7 × 999 ≡ 7 × 11 ≡ 1 mod 19

The other numbers G, it turns out, are 703 and 11286. Knowing those, we can go back and figure out the number x we were originally looking for, the one that generates a factor Z9 in U18981.

x = 4 × 6993 + 1 × 703 + 1 × 11286 = 39961 ≡ 1999

That's a lot of calculation, so it's nice that we can check the result by taking powers mod 18981 and verifying that 19999 ≡ 1.

I won't go through the other components in detail, but here are the results.

 qm 19 27 37 structure of Uqm Z2 × Z32 Z2 × Z32 Z22 × Z32 generator of Uqm 2 2 2 generator of Z9 22 = 4 22 = 4 24 = 16 G 6993 703 11286 generator in Un 1999 2110 17443

Although 2 happens to be a generator of Uqm in all three cases, I think that's just an accident. It's not a generator mod 7, for example.