Skip to content

Chapter 13: Group, Group Isomorphism, Cyclic Groups, Subgroups, Lagrange’s Theorem, Rings and Fields, Finite Fields

(RB1 C.L. Liu, Sections 48–56)

1. Group

Definition

A group ((G, )) is a set (G) with a binary operation () satisfying:

  1. Closure: (\forall a,b \in G, ; a*b \in G)
  2. Associativity: ((ab)c = a(bc), \forall a,b,c \in G)
  3. Identity Element: (\exists e \in G: ae = ea = a, \forall a \in G)
  4. Inverse Element: (\forall a \in G, \exists a^{-1} \in G: aa^{-1} = a^{-1}a = e)

Example 1: Integers under Addition

  • (G = \mathbb{Z}, * = +)
  • Identity = 0
  • Inverse = (-a)
  • Associative and closed ✅ → group

Example 2: Non-Example

  • Natural numbers (\mathbb{N}) under addition ❌
  • No additive inverse

2. Abelian (Commutative) Group

  • A group is Abelian if (ab = ba) for all (a,b \in G)

Example: ((\mathbb{Z},+)) ✅ Non-example: (2 \times 2) non-singular matrices under multiplication ❌

3. Group Isomorphism

Definition

Two groups ((G,)) and ((H,\cdot)) are isomorphic ((G \cong H)) if there exists a bijective function* (f: G \to H) such that:

[ f(a*b) = f(a) \cdot f(b), \forall a,b \in G ]

  • Essentially, same group structure, different labels

Example

  • ((\mathbb{Z}_4, +_4)) and (({1, i, -1, -i}, \cdot)) (complex 4th roots of unity)
  • Both cyclic, same structure → isomorphic

4. Cyclic Groups

Definition

A group (G) is cyclic if (\exists g \in G) (generator) such that:

[ G = {g^k \mid k \in \mathbb{Z}} ]

  • All elements can be expressed as powers of g

Example

  • ((\mathbb{Z}_6, +_6)) → generator 1
  • Elements: 0,1,2,3,4,5

5. Subgroups

Definition

A subset (H \subseteq G) is a subgroup if (H) is itself a group under the operation of (G).

  • Denoted: (H \le G)

Example

  • (G = (\mathbb{Z}, +), H = 2\mathbb{Z}) → even integers
  • Closed under +, identity 0, inverses exist ✅ → subgroup

6. Lagrange’s Theorem

Statement

If (H) is a finite subgroup of (G):

[ |H| ;|; |G| ]

  • Order of subgroup divides order of group

Example

  • (G = \mathbb{Z}_8, H = {0,4})
  • |G| = 8, |H| = 2 → 2 divides 8 ✅

7. Rings

Definition

A ring ((R, +, \cdot)) is a set (R) with two operations satisfying:

  1. ((R,+)) is an Abelian group
  2. ((R, \cdot)) is associative

  3. Distributive laws:

  4. (a\cdot(b+c) = a\cdot b + a\cdot c)

  5. ((a+b)\cdot c = a\cdot c + b\cdot c)

  6. If multiplication is commutative → commutative ring

  7. Ring with multiplicative identity → unitary ring

Example

  • Integers (\mathbb{Z}) under +, × → commutative, unitary ring
  • 2x2 matrices → ring (non-commutative)

8. Fields

Definition

A field (F) is a commutative ring with multiplicative inverses (except 0):

  • ((F, +)) → Abelian group
  • ((F \setminus {0}, \cdot)) → Abelian group

Example

  • (\mathbb{Q}, \mathbb{R}, \mathbb{C}) → fields
  • (\mathbb{Z}_p) with prime p → finite field

9. Finite Fields

  • Fields with finite number of elements
  • Denoted (\mathbb{F}_q) or (\mathbb{Z}_p)
  • Used in cryptography, coding theory, hashing

Example

  • (\mathbb{Z}_5 = {0,1,2,3,4})
  • Addition & multiplication modulo 5 → field

10. Applications in Computer Science

  • Cryptography (RSA, ECC) → finite fields
  • Error detection & correction → coding theory
  • Hash functions → modular arithmetic
  • Algebraic structures → data structures & algorithms

Comments