Algebraic structures: groups, rings and fields notes — Unit 3

An Algebraic Structure consists of a non-empty set $S$ equipped with one or more binary operations, along with axioms that these operations must satisfy.

⇒1.1 Binary Operation

A binary operation $\ast$ on a set $S$ is a function from $S \times S$ to $S$. This simply means that if you take any two elements from $S$ and apply the operation, the result must also be an element of $S$. This property is known as Closure.

• Example: Addition ($+$) is a binary operation on the set of Natural Numbers $\mathbb{N}$.
• Counter-example: Subtraction ($-$) is not a binary operation on $\mathbb{N}$, because $3 - 5 = -2$, and $-2 \notin \mathbb{N}$.

A binary operation $\ast$ on a set $S$ can exhibit several mathematical properties:

• Associative: For all $a, b, c \in S$, $(a \ast b) \ast c = a \ast (b \ast c)$.
• Commutative: For all $a, b \in S$, $a \ast b = b \ast a$.
• Identity Element: An element $e \in S$ such that for all $a \in S$, $a \ast e = e \ast a = a$. (e.g., $0$ for addition, $1$ for multiplication).
• Inverse Element: For a given $a \in S$, an element $a^{-1} \in S$ such that $a \ast a^{-1} = a^{-1} \ast a = e$. (e.g., $-a$ for addition, $1/a$ for multiplication).

Algebraic structures are classified based on which properties their binary operations satisfy.

⇒3.1 Groupoid (Magma)

A set $S$ with a binary operation $\ast$ that satisfies only Closure.

⇒3.2 Semi-group

A Groupoid that also satisfies the Associative property.
(Closure + Associativity).

⇒3.3 Monoid

A Semi-group that contains an Identity element.
(Closure + Associativity + Identity).

Example: The set of Natural numbers $\mathbb{N}$ under multiplication is a Monoid (identity is 1). But $\mathbb{N}$ under addition is only a Semi-group if we don't include 0 in $\mathbb{N}$.

A Group $(G, \ast)$ is a Monoid where every element has an Inverse.

⇒4.1 The Four Group Axioms

• 1. Closure: For all $a, b \in G$, $a \ast b \in G$.
• 2. Associativity: For all $a, b, c \in G$, $(a \ast b) \ast c = a \ast (b \ast c)$.
• 3. Identity: There exists $e \in G$ such that $a \ast e = e \ast a = a$.
• 4. Inverse: For every $a \in G$, there exists $a^{-1} \in G$ such that $a \ast a^{-1} = a^{-1} \ast a = e$.

⇒4.2 Abelian (Commutative) Group

A Group that also satisfies the Commutative property: $a \ast b = b \ast a$ for all $a, b \in G$.

Example: The set of Integers $\mathbb{Z}$ under addition is an Abelian Group. (Closure: yes. Assoc: yes. Identity: 0. Inverse: $-a$. Commutative: yes).

⇒5.1 Order of a Group

The Order of a Group $G$, denoted by $|G|$ or $O(G)$, is the number of elements in the set $G$. A group can be finite or infinite.

⇒5.2 Order of an Element

The Order of an element $a \in G$, denoted by $O(a)$, is the smallest positive integer $n$ such that $a^n = e$ (where $e$ is the identity element).

*Note: $a^n$ means applying the binary operation $n$ times: $a \ast a \ast a \dots$ If the operation is addition, it means $na = e$.*

If no such integer $n$ exists, the element is said to have infinite order.

A subset $H$ of a group $G$ is called a Subgroup if $H$ itself forms a group under the same binary operation defined on $G$.

⇒6.1 Subgroup Tests

To prove a subset $H$ is a subgroup, we don't need to check all four axioms. We can use simplified tests:

• Two-Step Test: $H$ is a subgroup if it is closed under the operation (if $a, b \in H$, then $a \ast b \in H$) AND closed under inverses (if $a \in H$, then $a^{-1} \in H$).
• One-Step Test: $H$ is a subgroup if for any $a, b \in H$, $a \ast b^{-1} \in H$.

Every group $G$ has at least two trivial subgroups: the group $G$ itself, and the subgroup consisting only of the identity element $\{e\}$.

A group $G$ is called Cyclic if there exists at least one element $g \in G$ such that every other element in the group can be generated by repeatedly applying the group operation on $g$.

The element $g$ is called a generator of the group, and we write $G = \langle g \rangle$.

For a multiplicative group: $G = \{g^n \mid n \in \mathbb{Z}\}$
For an additive group: $G = \{ng \mid n \in \mathbb{Z}\}$

⇒7.1 Properties of Cyclic Groups

• Every cyclic group is Abelian (commutative).
• Every subgroup of a cyclic group is also cyclic.
• If a group has a prime order, it must be cyclic.

Let $H$ be a subgroup of $G$, and let $a$ be any element in $G$.

⇒8.1 Left and Right Cosets

• Left Coset ($aH$): The set obtained by applying the operation between $a$ and every element of $H$. $aH = \{a \ast h \mid h \in H\}$
• Right Coset ($Ha$): $Ha = \{h \ast a \mid h \in H\}$

If $G$ is an Abelian group, the left and right cosets are always equal ($aH = Ha$).

⇒8.2 Properties of Cosets

• A coset is not necessarily a subgroup (it usually doesn't contain the identity).
• Two left cosets are either identical or completely disjoint (no common elements).
• The union of all distinct left cosets of $H$ is exactly the group $G$. Thus, cosets partition the group.

This is one of the most important theorems in group theory.

⇒9.1 Statement

Lagrange's Theorem: If $G$ is a finite group and $H$ is a subgroup of $G$, then the order of the subgroup $H$ divides the order of the group $G$.

Mathematically: $O(G) = k \cdot O(H)$, where $k$ is an integer (specifically, $k$ is the number of distinct cosets of $H$, called the index of $H$).

⇒9.2 Corollaries (Consequences)

• The order of any element $a \in G$ must divide the order of $G$.
• A group of prime order has no proper non-trivial subgroups (because a prime number has no divisors other than 1 and itself).
• Consequently, every group of prime order is cyclic.

A Ring $(R, +, \cdot)$ is an algebraic structure equipped with two binary operations, usually called addition ($+$) and multiplication ($\cdot$).

⇒10.1 Ring Axioms

• 1. Under Addition: $(R, +)$ must be an Abelian Group. (Closed, Associative, Identity $0$, Inverse $-a$, Commutative).
• 2. Under Multiplication: $(R, \cdot)$ must be a Semi-group. (Closed, Associative).
• 3. Distributive Laws: Multiplication distributes over addition. $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ and $(a + b) \cdot c = (a \cdot c) + (b \cdot c)$.

Example: The set of Integers $\mathbb{Z}$ under standard addition and multiplication forms a ring.

⇒11.1 Commutative Ring

A ring is commutative if its multiplication operation is commutative: $a \cdot b = b \cdot a$.

⇒11.2 Ring with Unity

A ring that contains a multiplicative identity element, usually denoted as $1$, such that $a \cdot 1 = 1 \cdot a = a$.

⇒11.3 Zero Divisors

In standard arithmetic, if $a \cdot b = 0$, then either $a = 0$ or $b = 0$. However, in some rings (like matrices or modulo arithmetic), you can have non-zero elements $a$ and $b$ such that $a \cdot b = 0$. These elements are called zero divisors.

⇒11.4 Integral Domain

A commutative ring with unity that has no zero divisors. (If $a \cdot b = 0$, then strictly $a=0$ or $b=0$).

A Field is the most highly structured algebraic system we study. It is essentially an Integral Domain where division is possible.

⇒12.1 Field Axioms

A Field $(F, +, \cdot)$ must satisfy:

• 1. Under Addition: $(F, +)$ is an Abelian Group (Identity is $0$).
• 2. Under Multiplication: $(F - \{0\}, \cdot)$ is an Abelian Group. This means every non-zero element must have a multiplicative inverse (allowing for division).
• 3. Distributive Laws: Multiplication distributes over addition.

Examples: Rational numbers $\mathbb{Q}$, Real numbers $\mathbb{R}$, and Complex numbers $\mathbb{C}$ are all fields. Integers $\mathbb{Z}$ is not a field because elements like $2$ do not have a multiplicative inverse in $\mathbb{Z}$ (1/2 is not an integer).

A field that contains a finite number of elements is called a Finite Field or a Galois Field.

⇒13.1 Modulo Prime Fields

The set of integers modulo a prime number $p$, denoted as $\mathbb{Z}_p$, forms a finite field.

Example: $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$ under addition and multiplication modulo 5 is a field. Every non-zero element has a multiplicative inverse.
- Inverse of 2 is 3 (because $2 \cdot 3 = 6 \equiv 1 \pmod 5$).
- Inverse of 4 is 4 (because $4 \cdot 4 = 16 \equiv 1 \pmod 5$).

⇒13.2 Non-Prime Modulo

If $n$ is a composite number (e.g., 6), then $\mathbb{Z}_n$ is a Ring, but not a Field. It will contain zero divisors. (In $\mathbb{Z}_6$, $2 \cdot 3 = 6 \equiv 0 \pmod 6$, yet neither $2$ nor $3$ is zero).

Algebraic structures build incrementally: from simple sets to Fields.

⇒14.1 University Exam Checklist

• Define Semi-group, Monoid, Group, and Abelian Group.
• Show that the set of integers modulo $n$ under addition is a cyclic group.
• State and prove Lagrange’s Theorem.
• Define an Integral Domain and a Field. Explain the difference between them.
• Prove that every finite integral domain is a field.
• Prove that the intersection of two subgroups is a subgroup.

⇒14.2 Application in Computer Science

• Cryptography: Finite Fields (specifically Galois Fields $GF(2^n)$) form the mathematical foundation of the Advanced Encryption Standard (AES).
• Public Key Cryptography: The RSA algorithm relies heavily on the properties of cyclic groups, prime factorization, and Euler's Totient function (which derives from group order).
• Error Correcting Codes: Reed-Solomon codes used in CDs, DVDs, and QR codes operate over finite fields to detect and correct data corruption.