Institut for Matematik og Datalogi Odense Universitet

{May 8, 1996 \atop JFB}

DM11 – F96 – Lecture 13

Lecture, May 1

We finished chapter 6, skipping topological sort, which is covered in DM02. We also covered Huffman codes.

Lecture, May 8

We will begin on some algebra. (See the notes for this below.)

Lecture, May 15

We will continue with algebra.

Problems to be discussed in week 21

• 11, 12, 13, and 14 from section 8.2.

• Perform the algorithm for Huffman encoding to produce the tree which would result from the following probabilities: 0.03, 0.04, 0.05, 0.11, 0.12, 0.14, 0.15, 0.17, 0.19.

• Prove that function composition is associative.

• Prove that modular addition and multiplication are associative.

• What is the order of the group S_{n}?

Algebra

1 The definition of a group

Def. A group is a set G closed under a binary operation ⊙ such that

• Associative Law: For all x, y, z ∈ G, x ⊙ (y ⊙ z) = (x ⊙ y) ⊙ z.

• Identity: There is an element e ∈ G, called the identity, such that for all x ∈ G, e ⊙ x = x ⊙ e = x.

• Inverse: For every x ∈ G, there exists a y ∈ G such that x ⊙ y = y ⊙ x = e. This y is the inverse of x. We write y = x^{−1}.

When referring to groups in general, rather than to any specific example of a group, the binary operation is called multiplication and the result x ⊙ y is called a product. The notation x^{n} is used to represent x ⊙ x ⊙ ... ⊙ x, where x appears n times. There are many examples of groups.

Example: The integers ZZ under addition. The associative law holds. The identity is 0. The inverse of n ∈ ZZ is −n. Note that the reals IR are also a group under addition, as are the rationals IQ.

Example: IR−{0} under multiplication. The associative law holds. The identity is 1. The inverse of x ∈ IR is 1/x. IQ−{0} is also a group under multiplication, but the integers are not, since 2, for example does not have a multiplicative inverse.

These first examples were infinite groups. The next examples are finite groups. The number of elements in a group G, written |G|, is the order of the group.

Example: ZZ_{n}, the integers modulo n, under addition. The set is the integers {0, 1, 2, ..., n − 1}, and the addition operation is defined so that

a ⊙ b = a + b (mod n).

Note that the result is always in ZZ_{n}. A group must be closed under its operation, i.e. the result of applying the operation to two elements of the group must be in the group. It is easy to check that the associative law holds. The identity is 0. The inverse of x ∈ ZZ_{n} is n − x. The order of ZZ_{n} is n.

Example: ZZ_{n}^{∗}, the positive integers less than n which are relatively prime to n, under multiplication. The operation is defined so that

a ⊙ b = a · b (mod n).

The set is closed because if x, y ∈ ZZ_{n}^{∗} and x ⊙ y = z, then there is an integer k such that x · y = z + kn. If d = gcd(z, n), then d divides z + kn, so d divides x · y.

But x and y are relatively prime to n, so d must be 1 and z ∈ ZZ_{n}^{∗}. It is easy to check that the operation is associative. The identity is 1. The inverse exists by Theorem 3 of section 2.5 in the textbook. The order of ZZ_{n}^{∗} is ϕ(n), where ϕ is the Euler ϕ-function, and its value at n is the number of positive integers less than n which are relatively prime to n.

The above examples are all abelian groups because the operation is commutative: x ⊙ y = y ⊙ x for all x, y in the group. Not all groups are abelian.

Example: S_{n}, the symmetric group on n letters, is the set of permutations of the set {1, 2, ..., n}. Let n = 5 and consider the permutation σ = (2, 1, 5, 3, 4). This

can be written as ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 5 & 3 & 4 \end{matrix} ), and defines the function σ(1) = 2, σ(2) = 1,

σ(3) = 5, σ(4) = 3, σ(5) = 4. Let η = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 4 & 3 & 2 \end{matrix} ). Composing the

functions σ and η gives ση(1) = σ(5) = 4, ση(2) = σ(1) = 2, ση(3) = σ(4) = 3,

ση(4) = σ(3) = 5, and ση(5) = σ(2) = 1. So ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 5 & 3 & 4 \end{matrix} ) ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 4 & 3 & 2 \end{matrix} ) =

( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 5 & 1 \end{matrix} ). Since function composition is associative, the composition of

permutations is an associative operation. Note that ησ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 2 & 4 & 3 \end{matrix} ) ≠

ση, so composition of permutations is not necessarily commutative. This compo-

sition of permutations is the operation in S_{n}. The identity is ( \begin{matrix}1 & 2 & ... & n \\ 1 & 2 & ... & n \end{matrix} ). If

σ = ( \begin{matrix}1 & 2 & ... & n \\ i_{1} & i_{2} & ... & i_{n} \end{matrix} ) and η = ( \begin{matrix}i_{1} & i_{2} & ... & i_{n} \\ 1 & 2 & ... & n \end{matrix} ), then ση = ησ = ( \begin{matrix}1 & 2 & ... & n \\ 1 & 2 & ... & n \end{matrix} ),

so every element has an inverse. Thus, S_{n} is a group, but it is not an abelian group.

Consider the permutation σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 5 & 3 & 4 \end{matrix} ). This is composed of two cycles

1 → 2 → 1 and 3 → 5 → 4 → 3, so this permutation σ can also be written as a product of cycles: (12)(354). In fact any permutation can be written similarly as a product of cycles. For a permutation (1)(2)(34)(5), we often just write (34); any integers which form cycles of length 1 are fixed, and they are not listed when the permutation is written as a product of cycles. A transposition is a cycle of length 2, (ij). Note that one can compose transpositions, as one composes permutations, since they are permutations. Thus the product (45) ⊙ (34) is the cycle (354), so σ = (12) ⊙ (45) ⊙ (34). A permutation is even if and only if it can be expressed as a product of an even number of transpositions.

If the underlying set which gets permuted is some finite set X, not necessarily the same as {1, 2, ..., n}, then the set of permutations of the elements of X is clearly also a group under composition. This group is called the symmetric group of X and can be denoted Sym(X).

2 Subgroups

Def. Let G be a group and H be a subset of G. Then, H is a subgroup of G if H itself is a group with respect to the operation in G. The order of a subgroup is its cardinality.

Suppose G is a group and H ⊆ G. Then H is a subgroup of G if and only if the following hold:

• For all x, y ∈ H, x ⊙ y ∈ H. (H is closed under the group operation.)

• The identity is in H.

• For every x ∈ H, x^{−1} ∈ H.

Note that associativity was not mentioned here; H automatically inherits that from the group G. If H is known to be nonempty, it is unnecessary to mention that the identity must be in H, since that is implied by the other two properties.

Example: Any group is a subgroup of itself.

Example: The subset of any group, G, which consists of only the identity element is a subgroup of G.

Example: The even integers are a subgroup of the integers under addition.

Example: The set \{( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{matrix} ) , ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 4 & 3 & 5 \end{matrix} )\} is a subgroup of

S_{5}.

Example: It can be shown that the subset A_{n} of the symmetric group S_{n}, which contains all even permutations on n letters, is a subgroup of S_{n}. It is called the alternating group on n letters.

Example: The set {0, 5, 10} is a subgroup of ZZ_{15} under addition.

Example: The set {1, 2, 4} is a subgroup of ZZ_{7}^{∗}.

Thm. Suppose S is a nonempty collection of subgroups of a group G. Let H′ = ⋂_{H∈S} H. Then H′ is a subgroup of G. Pf. Suppose x, y ∈ H′. Then x, y ∈ H for all H ∈ S. Since each of the subgroups in S must themselves be closed under the group operation, x ⊙ y ∈ H for all H ∈ S, so x ⊙ y ∈ H′. Thus H′ is closed under the group operation. The identity is in H′ since it must be in every subgroup H ∈ S. Suppose x ∈ H′. Then x^{−1} must also be in H′ since it must be in each of the subgroups in S. □

3 Generators

Def. Let H be a subset of a group G, and let S be the collection of all subgroups of G which contain H. Then, <H>= ⋂_{G′∈S} G′ is the subgroup generated by H.

Suppose H is a subset of a group G. Consider all products h_{1} ⊙ h_{2} ⊙ ... ⊙ h_{n}, where h_{i} or h_{i}^{−1} is an element of H for all i (the h_{i} are not necessarily all distinct). The set of all these products is clearly a subgroup of G, and any subgroup of G containing H must contain all these elements, so this set is <H>, the subgroup generated by H.

Def. A group or subgroup is said to be cyclic if it is generated by a single element. An element which generates a cyclic group or subgroup is called a generator or primitive element.

Note that a group G with identity e is cyclic if and only if it is of the form {..., g^{−2}, g^{−1}, g^{0} = e, g^{1}, g^{2}, ...}, since if it is a product of t copies of g and s copies of g^{−1} in any order, the result is g^{t−s} if t ≥ s and (g^{−1})^{s−t} otherwise.

Def. The order of an element of a group G is the order of the subgroup that element generates.

Thm. Suppose G is a group with identity e, and g ∈ G has finite order m. Then m is the least positive integer such that g^{m} = e. Pf. Since g generates a finite subgroup, there exist positive integers s, t with s < t such that g^{s} = g^{t}. (Otherwise, the subgroup generated would be infinite.) Consider g^{t−s} = g^{t}(g^{−1})^{s} = g^{s}(g^{−1})^{s} = e. This shows that there exists at least one positive integer t − s such that g^{t−s} = e. Let k be the smallest positive integer such that g^{k} = e. Suppose r ≥ k. Then r can be written as r = ik + j, where i and j are nonnegative integers, such that j ≤ k − 1. Since g^{r} = g^{ik+j} = g^{ik}g^{j} = (g^{k})^{i}g^{j} = e^{i}g^{j} = eg^{j} = g^{j}, any element g^{r} where r ≥ k is in the set H = {e = g^{0}, g^{1}, g^{2}, ..., g^{k−1}} ⊆<g>. Note that this set H contains k distinct elements, since if g^{i} = g^{j}, with 0 ≤ i < j ≤ k − 1, then r = j − i < k is a smaller positive integer such that g^{r} = e. But k was the smallest, so all these powers must be distinct. Suppose x ∈<g>. Then there is some nonnegative integer r such that x = g^{r} or x = (g^{−1})^{r}. We have already argued that if x = g^{r}, then x ∈ H, so suppose that x = (g^{−1})^{r}. Let d be the smallest integer such that kd ≥ r. Then g^{kd−r} ∈ H, but g^{kd−r} = (g^{k})^{d}(g^{−1})^{r} = (g^{−1})^{r}. Hence <g>⊆ H, and so H =<g>. Since |H| = k, we have that <g>= k, which is the least positive integer such that g^{k} = e. □

Example: The set {2} generates the subgroup {1, 2, 4} of ZZ_{7}^{∗}. Thus, it is a cyclic subgroup, and the order of the element 2 is 3. The set {3} generates all of ZZ_{7}^{∗}, so it is a cyclic group. In fact, it can be shown that ZZ_{p}^{∗} is cyclic whenever p is prime.

4 Lagrange’s Theorem

Def. Let H be a subgroup of G and x ∈ G. Then, Hx = {h ⊙ x | h ∈ H} is a right coset of H in G.

Lemma Let H be a subgroup of G. All right cosets of H contain |H| elements. Pf. Clearly for any x, Hx contains at most |H| elements. If it contains fewer than |H| elements, there must be two distinct elements h_{1}, h_{2} ∈ H such that h_{1} ⊙ x = h_{2} ⊙ x. But multiplying on the right by x^{−1} gives h_{1} = h_{2}. Thus, every element of H is mapped onto a different element of G when multiplied on the right by x ∈ G, so |Hx| = |H|. □

Consider the subgroup H = {1, 2, 4} of ZZ_{7}^{∗}. The right cosets of H are H ⊙1 = H, H ⊙2 = H, H ⊙3 = {3, 5, 6}, H ⊙4 = H, H ⊙5 = {3, 5, 6}, and H ⊙6 = {3, 5, 6}. So any two cosets are either identical or disjoint. This holds in general; the collection of cosets of a subgroup H of G is a partition of the group G. Thus, the relation R = {(a, b) | a and b are in the same right coset of H} is an equivalence relation.

Lemma Let H be a subgroup of G, x, y ∈ G. Then either Hx = Hy or Hx∩Hy = ∅. Pf. Suppose that Hx∩Hy ≠ ∅. Then there is some b ∈ Hx∩Hy, so b = h_{1} ⊙x = h_{2} ⊙ y for some h_{1}, h_{2} ∈ H. Thus, x = h_{1}^{−1} ⊙ h_{2} ⊙ y, and Hx = H(h_{1}^{−1} ⊙ h_{2} ⊙ y). Hence any element of Hx is of the form h⊙(h_{1}^{−1} ⊙h_{2} ⊙y) = (h⊙h_{1}^{−1} ⊙h_{2})⊙y for some h ∈ H. Since H is a subgroup, h⊙h_{1}^{−1} ⊙h_{2} ∈ H, so (h⊙h_{1}^{−1} ⊙h_{2})⊙y ∈ Hy. Thus, Hx ⊆ Hy. Since, by the previous lemma, the two cosets have the same size, they must be equal. So if Hx ∩ Hy ≠ ∅, then Hx = Hy. □

These two lemmas tell us that the group G must be a disjoint union of right cosets of any subgroup H, all of which have the same size. This gives us the following:

Thm. [Lagrange] If G is a finite group and H is any subgroup of G, then the order of H divides the order of G.

Corollary Let G be a finite group and g ∈ G. The order of the element g divides the order of the group G.

Corollary Suppose |G| = n and g ∈ G. Then g^{n} = e, where e is the identity in G. Pf. Let s be the order of the subgroup generated by g. By a previous theorem, g^{s} = e, where e is the identity. By Lagrange’s Theorem, s divides n, so there is an integer c such that n = sc. Note that g^{n} = g^{sc} = (g^{s})^{c} = e^{c} = e, so the corollary follows. □

Recall Fermat’s Little Theorem from section 2.5 of the textbook. It becomes much easier to prove using a little bit of group theory.

Thm. [Fermat’s Little Theorem] If p is prime and a is an integer not divisible by p, then a^{p−1} ≡ 1 (mod p). Pf. Consider the multiplicative group ZZ_{p}^{∗}. This contains the positive integers less than p which are relatively prime to p. Since p is prime, all integers between 1 and p − 1 are relatively prime to p. Thus, the order of ZZ_{p}^{∗} is p − 1. By the previous corollary, for any a in this group, a^{p−1} ≡ 1 (mod p), so this holds for any integer a which when reduced modulo p is between 1 and p − 1. This is any integer not divisible by p. □

Using this same group theory, we can more easily show that encryption with RSA, followed by decryption with RSA yields the original message, if the message is less than n and relatively prime to n. (The other cases can be proven using group theory and the Chinese Remainder Theorem by considering all the cases separately.) Recall that n = pq where p and q are large primes. Then, |ZZ_{n}^{∗}| = ϕ(n) = (p − 1)(q − 1) (one can get this using the Principle of Inclusion-Exclusion — see problems 22 and 23 on page 348). If the message M is less than n and relatively prime to n, M ∈ ZZ_{n}^{∗}. Recall that ed ≡ 1 (mod (p − 1)(q − 1)), so there is an integer k such that ed = 1 + k(p − 1)(q − 1). If C ≡ M^{e} (mod n), then C^{d} ≡ (M^{e})^{d} ≡ M^{ed} ≡ M^{1+k(p−1)(q−1)} ≡ M · M^{k(p−1)(q−1)} ≡ M · (M^{ϕ(n)})^{k} ≡ M · 1^{k} ≡ M (mod n).

5 Rings and fields

The integers and real numbers have two operations addition and multiplication which can be considered together. For example, there is a distributive law which says that x(y + z) = xy + xz. Groups are generalizations of sets which have one “nice” operation; rings and fields are generalizations of sets which have two “nice” operations.

Def. A ring is a set R closed under two binary operations + and • such that

• R1. R is an abelian group with respect to the operation +.

• R2. The operation • is associative.

• R3. [Distributive Laws] For all x, y, z ∈ R, the following hold:

\begin{aligned}x • (y + z) & = x • y + x • z \\ (y + z) • x & = y • x + z • x \end{aligned}

The first operation + is called addition and the second operation • is called multiplication.

Note that any ring must contain at least one element since it contains an identity with respect to addition. One can define a ring with just one element 0. Then 0 + 0 = 0 and 0 • 0 = 0. This is called the trivial ring. A nontrivial ring is a ring with more than one element. The identity element with respect to addition is called zero, and all other elements are called nonzero elements. If the ring R has an identity element i with respect to multiplication, then for all x ∈ G, i • x = x • i = x, and R is said to be a ring with identity. This identity is denoted by 1. The ring R is commutative if for all x, y ∈ R, x • y = y • x. Note that the integers and the reals are both commutative rings with identity.

Def. A field is a nontrivial commutative ring with identity in which every nonzero element has a multiplicative inverse.

Examples: IR is a field and IQ is a field, but ZZ is not because 2, for instance, does not have a multiplicative inverse.

Example: ZZ_{n} is a field when n is prime. It is a ring when n is composite, but it is not a field. To see this, consider p which divides n, where 1 < p < n. Suppose n = pr. This element p is in the ring ZZ_{n}, but it does not have a multiplicative inverse because it is not relatively prime to n. The element r is also in the ring ZZ_{n}. Note that p • r ≡ 0 (mod n), so p and r are called zero divisors. Any element which is relatively prime to n, though, has an inverse.