The Structure of Z_n

The Structure of U_n
Multiplication in Base 7

Unfortunately I haven't used the symbol Z_n consistently. Sometimes (mainly in Multiplication in Base 7) it means the group of integers under addition mod n, but most of the time it means that I'm considering isomorphic groups to be the same and talking about the unique cyclic group of order n without thinking of its elements as specifically integers. Sorry for any confusion!

For the arguments I want to make here, I'd like to think of Z_n as an abstract cyclic group of order n. Let's say it has an identity element e and a generator a such that aⁿ = e.

Orders of Elements

For various reasons, it will be useful to understand the orders of the elements of Z_n. What does that even mean? Well, the word “order” can be used in two different ways. We say a group has order n, meaning that it has n elements, but we also say an element x has order m, meaning that m is the smallest number such that x^m = e. In symbols, o(x) = m.

We already know o(a) = n, by definition. What about o(a²)? If n is even, then the powers of a² include aⁿ,

(a²)^n/2 = aⁿ = e,

and therefore o(a²) = n/2. But, if n is odd, then the powers of a² skip over aⁿ and go all the way up to a²ⁿ,

(a²)ⁿ = a²ⁿ = (aⁿ)² = e² = e,

and therefore o(a²) = n.

What about the general case, o(a^k)? To get (a^k)^m = a^km = e, we need km to be a multiple of n. The k part can provide whatever factors k and n have in common, then the m part has to provide the rest. And what factors do k and n have in common? Exactly (k,n), the greatest common divisor of k and n; consequently o(a^k) = m = n/(k,n).

Let's look at a couple of examples. If n is prime, say n = 7, there are no common factors and the orders are all the same.

k	0	1	2	3	4	5	6
o(ak)	1	7	7	7	7	7	7

On the other hand, if n is composite, say n = 12, there are plenty of common factors and we get a nice pattern.

k	0	1	2	3	4	5	6	7	8	9	10	11
o(ak)	1	12	6	4	3	12	2	12	3	4	6	12

The positions of the 12s is a clue leading to the fact that these statements are all equivalent.

k and n are relatively prime
k and n have no common factors
(k,n) = 1
o(a^k) = n
a^k is a generator of the group

Finally, here's a pair of results about orders of elements.

• The order of an element is always a divisor of the order of the group. This is actually a basic result of group theory that applies to all groups.
• Conversely, for any divisor d of the order of the group, there is at least one element with that order, namely a^n/d. This part only applies to cyclic groups (because if it applies, then we can take d = n and obtain a generator).

Subgroups

Here's a very similar pair of results about orders of subgroups.

• The order of a subgroup is always a divisor of the order of the group. This is also a basic result of group theory that applies to all groups.
• Conversely, for any divisor d of the order of the group, there is exactly one subgroup with that order, and it's cyclic, namely the subgroup generated by a^n/d. Proof is below. This part also only applies to cyclic groups (because if it applies, then the “subgroup” with order n is cyclic).

It's pretty clear that the subgroup generated by a^n/d is cyclic and has order d, so we have all the subgroups we need. The interesting question is, how do we know there aren't any other subgroups (that we don't need)? Well, suppose we have an arbitrary subgroup of Z_n. What can we say about it? Does it contain anything besides the identity element e? If not, that's the case d = 1, and we're done. Otherwise, let k be the smallest positive number such that a^k is a member of the subgroup. But then consider the powers of a^k.

1. k has to be a divisor of n, or else the powers will wrap around at n and produce a remainder less than k.
2. The subgroup can't contain any other elements, or else we'd be able to remove powers of a^k and produce a remainder less than k.

And that's the case d = n/k. By the way, that kind of argument is very common in algebra and number theory.

Some Theory

A homomorphism is a function from one group to another that commutes with group multiplication, like so.

f(xy) = f(x)f(y)

A homomorphism always maps the identity element e in one group to the identity element ê in the other group.

f(e) = f(e)ê = f(e)[f(e)f(e)⁻¹] = [f(e)f(e)]f(e)⁻¹ = f(e²)f(e)⁻¹ = f(e)f(e)⁻¹ = ê

A homomorphism that originates from Z_n is completely determined by f(a) because the definition of homomorphism makes f(a^k) = f(a)^k. Does that mean we can construct a homomorphism by setting f(a) to whatever we want? Not quite. Because o(a) = n, we have the constraint

f(a)ⁿ = f(aⁿ) = f(e) = ê,

which means that o(f(a)) has to be a divisor of n.

A homomorphism that's also a one-to-one correspondence is called an isomorphism. Groups that are isomorphic are essentially the same. Any two cyclic groups with the same order are isomorphic; that's the source of the confusion I was talking about at the start of the essay.

Technical detail that I feel compelled to include: by “one-to-one correspondence” I mean a function that's both one-to-one and onto, like in set theory when you're proving that two sets have the same cardinality.

An isomorphism from a group back to itself is called an automorphism. For example, for any element g we can define the function f_g(x) = gxg⁻¹, “conjugation by g” (see Conjugates). The function is a homomorphism because

f_g(xy) = gxyg⁻¹ = gxeyg⁻¹ = gx(g⁻¹g)yg⁻¹ = (gxg⁻¹)(gyg⁻¹) = f_g(x)f_g(y),

and you can check that it's one-to-one and onto, therefore it's an automorphism.

The set of automorphisms of a group is itself a group. How do we take the product of two automorphisms f₁ and f₂? Well, the product needs to be an automorphism, which first of all means it needs to be a function, and we define that function to be (f₁f₂)(x) = f₁(f₂(x)). The function is a homomorphism because

(f₁f₂)(xy) = f₁(f₂(xy)) = f₁(f₂(x)f₂(y)) = f₁(f₂(x))f₁(f₂(y)) = (f₁f₂)(x)(f₁f₂)(y),

and you can check that it's one-to-one and onto, therefore it's an automorphism.

Coming back to conjugation, here's an interesting fact.

f_gh(x) = (gh)x(gh)⁻¹ = ghxh⁻¹g⁻¹ = g(hxh⁻¹)g⁻¹ = gf_h(x)g⁻¹ = f_g(f_h(x)) = (f_gf_h)(x)

The functions f_gh and f_gf_h are the same at every point, so they're the same as functions.

f_gh = f_gf_h

You can probably see where this is going, but just to make everything perfectly clear, let's define a function C from the group under consideration to the group of automorphisms of that group by C(g) = f_g. Then we have the following.

C(gh) = C(g)C(h)

Yes, it's another homomorphism. But that's all I'm going to say about conjugation, because in abelian groups like Z_n, gxg⁻¹ = xgg⁻¹ = xe = x, so conjugation does nothing.

Automorphisms

Now we have everything we need to find all the automorphisms of Z_n.

Any homomorphism from Z_n back to itself is completely determined by f(a), but there are only n possible values for f(a), so there are only n possible homomorphisms: f_k(a) = a^k for 0 ≤ k < n. They all satisfy the constraint f_k(a)ⁿ = e, so they all really are homomorphisms.

Which ones are also automorphisms? The only remaining condition is that f_k should be one-to-one and onto. But, that obviously happens if and only if f_k(a) = a^k is a generator, and from above we know that happens if and only if k is relatively prime to n.

So, those are the automorphisms of Z_n. How do they combine? By multiplication!

(f_jf_k)(a) = f_j(f_k(a)) = f_j(a^k) = f_j(a)^k = (a^j)^k = a^jk = (f_jk)(a)

Unfortunately, there's a flaw in that equation, which is that jk might not fall into the range 0 ≤ jk < n. But, because aⁿ = e, we can subtract multiples of n from jk to get it into the correct range. Then the equation ends like this.

(f_jf_k)(a) = … = a^jk = a^{jk mod n} = (f_{jk mod n})(a)

Therefore the two sides are the same as functions.

f_jf_k = f_{jk mod n}

Then we can define a function M from the group U_n of integers relatively prime to n under multiplication mod n to the group of automorphisms of Z_n by M(k) = f_k and see that the two groups are isomorphic.

M(j)M(k) = M(jk mod n)

In other words, since isomorphic groups are essentially the same, the group of automorphisms of Z_n is U_n!

About that “mod” operation, please see the first part of Reduction Rules. The fact that I'm using it here in a mathematical context means that I failed to find a more elegant approach.

The last piece of the puzzle is, what exactly does the action of U_n on Z_n look like? The answer will be more compelling if we cast it in terms of the original definition of Z_n. So, let's define one more function, the natural isomorphism N from Z_n the group of integers under addition mod n to Z_n the abstract cyclic group of order n, N(k) = a^k. Then we have the following.

M(j)N(k) = f_j(a^k) = f_j(a)^k = (a^j)^k = a^jk = a^{jk mod n} = N(jk mod n)

Apply N⁻¹ to both sides, and here's what it says. If we have integers j in U_n and k in Z_n, we can move them over to abstract cyclic group land, let j act on k, and move the result back, and what we end up with is the product jk mod n. That is, U_n acts on Z_n by multiplication.

Finally, I'd like to point out that you can repeat the whole argument above without the “relatively prime” condition. The homomorphisms from Z_n back to itself form what's called a monoid. They combine by multiplication and are isomorphic to the monoid of integers under multiplication mod n. And they act on Z_n by multiplication. But, at that point you might as well admit that you're talking about the ring of integers mod n.