An Example

For my example, I'll find the smallest group U_n that contains the group G = ( Z₉ )³—that is, three factors Z_p^k 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₉.

How does one do that? Well, the place to start is in the component groups U₁₉, U₂₇, and U₃₇. The group U₁₉, 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₁₈, though, just a generator of the factor Z₉ … and for that we can use 2² = 4, since that generates only the even powers of two.

Now that we've found a generator for Z₉ in the component group U₁₉, the next step is to locate a copy of U₁₉ inside the main group U₁₈₉₈₁ 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
x ≡ 1 mod 27
x ≡ 1 mod 37.

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 ≡ δ_ij 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
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 ≡ 2¹², so that the inverse is 2⁶ ≡ 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₉ in U₁₈₉₈₁.

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⁹ ≡ 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 U_q^m in all three cases, I think that's just an accident. It's not a generator mod 7, for example.