Finite groups

A group (S, ⊕) is a set S together with a binary operation ⊕ defined on S for which the following properties hold.

1. Closure: For all a, b ∈ S, we have a ⊕ b ∈ S.

2. Identity: There is an element e ∈ S, called the identity of the group, such that e ⊕ a = a ⊕ e = a for all a ∈ S.

3. Associativity: For all a, b, c ∈ S, we have (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c).

4. Inverses: For each a ∈ S, there exists a unique element b ∈ S, called the inverse of a, such that a ⊕ b = b ⊕ a = e.

As an example, consider the familiar group (Z, +) of the integers Z under the operation of addition: 0 is the identity, and the inverse of a is -a. If a group (S, ⊕) satisfies the commutative law a ⊕ b = b ⊕ a for all a, b ∈ S, then it is an abelian group. If a group S, ⊕) satisfies |S| < ∞, then it is a finite group.

The groups defined by modular addition and multiplication

We can form two finite abelian groups by using addition and multiplication modulo n, where n is a positive integer. These groups are based on the equivalence classes of the integers modulo n, defined in Section 31.1.

To define a group on Z_n, we need to have suitable binary operations, which we obtain by redefining the ordinary operations of addition and multiplication. It is easy to define addition and multiplication operations for Z_n, because the equivalence class of two integers uniquely determines the equivalence class of their sum or product. That is, if a ≡ a′ (mod n) and b ≡ b′ (mod n), then

Thus, we define addition and multiplication modulo n, denoted +_n and ·_n, as follows:

(Subtraction can be similarly defined on Z_n by [a]_n -_n [b]_n = [a-b]_n, but division is more complicated, as we shall see.) These facts justify the common and convenient practice of using the least nonnegative element of each equivalence class as its representative when performing computations in Z_n. Addition, subtraction, and multiplication are performed as usual on the representatives, but each result x is replaced by the representative of its class (that is, by x mod n).

Using this definition of addition modulo n, we define the additive group modulo n as (Z_n, +_n). This size of the additive group modulo n is |Z_n| = n. Figure 31.2(a) gives the operation table for the group (Z₆, +₆).

Using the definition of multiplication modulo n, we define the multiplicative group modulo n as (). The elements of this group are the set of elements in Z_n that are relatively prime to n:

To see that is well defined, note that for 0 ≤ a < n, we have a ≡ (a + kn) (mod n) for all integers k. By Exercise 31.2-3, therefore, gcd(a, n) = 1 implies gcd(a + kn, n) = 1 for all integers k. Since [a]_n = {a + kn : k ∈ Z}, the set is well defined. An example of such a group is

where the group operation is multiplication modulo 15. (Here we denote an element [a]₁₅ as a; for example, we denote [7]₁₅ as 7.) Figure 31.2(b) shows the group (). For example, 8·11 ≡ 13 mod 15), working in . The identity for this group is 1.

As an example of computing multiplicative inverses, suppose that a = 5 and n = 11. Then EXTENDED-EUCLID(a, n) returns (d, x, y) = (1, -2, 1), so that 1 = 5 · (-2) + 11 · 1. Thus, -2 (i.e., 9 mod 11) is a multiplicative inverse of 5 modulo 11.

When working with the groups (Z_n, +_n) and () in the remainder of this chapter, we follow the convenient practice of denoting equivalence classes by their representative elements and denoting the operations +_n and ·_n by the usual arithmetic notations + and · (or juxtaposition) respectively. Also, equivalences modulo n may also be interpreted as equations in Z_n. For example, the following two statements are equivalent:

As a further convenience, we sometimes refer to a group (S, ⊕) merely as S when the operation is understood from context. We may thus refer to the groups (Z_n, +_n) and () as Z_n and , respectively.

The (multiplicative) inverse of an element a is denoted (a^-1 mod n). Division in is defined by the equation a/b ≡ ab^-1 (mod n). For example, in we have that 7^-1 ≡ 13 (mod 15), since 7 · 13 ≡ 91 ≡ 1 (mod 15), so that 4/7 ≡ 4 · 13 ≡ 7 (mod 15).

The size of is denoted φ(n). This function, known as Euler's phi function, satisfies the equation

where p runs over all the primes dividing n (including n itself, if n is prime). We shall not prove this formula here. Intuitively, we begin with a list of the n remainders {0, 1, ..., n - 1} and then, for each prime p that divides n, cross out every multiple of p in the list. For example, since the prime divisors of 45 are 3 and 5,

If p is prime, then , and

If n is composite, then φ(n) < n - 1.

Subgroups

If (S, ⊕) is a group, S′ ⊆ S, and (S′, ⊕) is also a group, then (S′, ⊕) is said to be a subgroup of (S, ⊕). For example, the even integers form a subgroup of the integers under the operation of addition. The following theorem provides a useful tool for recognizing subgroups.

For example, the set {0, 2, 4, 6} forms a subgroup of Z₈, since it is nonempty and closed under the operation + (that is, it is closed under +₈).

The following theorem provides an extremely useful constraint on the size of a subgroup; we omit the proof.

A subgroup S′ of a group S is said to be a proper subgroup if S′ ≠ S. The following corollary will be used in our analysis of the Miller-Rabin primality test procedure in Section 31.8.

Subgroups generated by an element

Theorem 31.14 provides an interesting way to produce a subgroup of a finite group (S, ⊕): choose an element a and take all elements that can be generated from a using the group operation. Specifically, define a^(k) for k ≥ 1 by

For example, if we take a = 2 in the group Z₆, the sequence a⁽¹⁾, a⁽²⁾, ...is 2, 4, 0, 2, 4, 0, 2, 4, 0, ... .

In the group Z_n, we have a^(k) = ka mod n, and in the group , we have a^(k) = a^k mod n. The subgroup generated by a, denoted 〈a〉 or (〈a〉, ⊕), is defined by

〈a〉 = {a^(k) : k ≥ 1}.

We say that a generates the subgroup 〈a〉 or that a is a generator of 〈a〉. Since S is finite, 〈a〉 is a finite subset of S, possibly including all of S. Since the associativity of ⊕ implies

a⁽ⁱ⁾ ⊕ a^(j) = a^{(i + j)},

〈a〉 is closed and therefore, by Theorem 31.14, 〈a〉 is a subgroup of S. For example, in Z₆, we have

Similarly, in , we have

The order of a (in the group S), denoted ord(a), is defined as the smallest positive integer t such that a^(t) = e.

It is consistent with the above corollary to define a⁽⁰⁾ as e and a⁽ⁱ⁾ as a^{(i mod t)}, where t = ord(a), for all integers i.