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 U_{n} The Proof

An ExampleFor my example, I'll find the smallest group U_{n} that contains the group G = ( Z_{9} )^{3}—that is, three factors Z_{pk} with p = 3 and k = 2. We can obtain one factor by taking q = p and m = k+1, so that q^{m} = 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 Z_{9}. How does one do that? Well, the place to start is in the component groups U_{19}, U_{27}, and U_{37}. The group U_{19}, 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 Z_{18}, though, just a generator of the factor Z_{9} … and for that we can use 2^{2} = 4, since that generates only the even powers of two. Now that we've found a generator for Z_{9} in the component group U_{19}, the next step is to locate a copy of U_{19} inside the main group U_{18981} 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,e_{B}), where e_{B} 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 I claimed, back in The Structure of U_{n}, 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 ≡ a_{i} mod m_{i}, where the factors m_{i} are relatively prime. If we can find a set of numbers G_{i} that satisfy
G_{i} ≡ delta(i,j) mod m_{j}, then the solution x can be obtained by adding up appropriate multiples.
x = sum ( a_{i} G_{i} ) (I don't know an official name for the numbers G_{i}, so I used the letter “G” because they remind me of Green's functions.) It turns out, fortunately, that the numbers G_{i} are quite easy to determine. The number G corresponding to the factor 19, for example, needs to satisfy the equations
G ≡ 1 mod 19 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 ≡ 2^{12}, so that the inverse is 2^{6} ≡ 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 Z_{9} in U_{18981}.
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 1999^{9} ≡ 1. I won't go through the other components in detail, but here are the results.
Although 2 happens to be a generator of U_{qm} in all three cases, I think that's just an accident. It's not a generator mod 7, for example.

See AlsoNumbers Odds and Ends Theorem on Finite Abelian Groups, A @ May (2001) 