About This Site
Game Theory Section
> A Theorem on Finite Abelian Groups
The Structure of Un
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
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
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.
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.
Odds and Ends
Theorem on Finite Abelian Groups, A
@ May (2001)