5.2 Cyclic Groups, Generators, Subgroups & Lagrange's Theorem

Back to Discrete Mathematics Notes

📚Module 05: Group Theory & Algebraic StructuresTopic 5.2: Cyclic Groups, Generators, Subgroups & Lagrange's Theorem⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Gear Trains & Modular Clock Hand Trajectories

Imagine a single cogwheel gear or clock hand:

1. The Generator & Cyclic Group: A clock hand with 12 positions. If you advance the hand by 1 hour repeatedly, you visit every single position on the clock face ($1, 2, 3, \dots, 12$) before returning home. The step of $1$ generates the entire cycle! What if you step by 5 hours at a time? $5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 12$—it also visits every position because $\gcd(5, 12) = 1$! Any element whose repeated powers generate the whole group is a generator, and the group is cyclic.
2. Subgroups (Synchronized Sub-Cycles): If you step by 3 hours, you only visit $\{3, 6, 9, 12\}$. That sub-loop is self-contained: it has closure, its own identity ($12$), and inverses. It forms a subgroup!
3. Lagrange's Law of Divisibility: Notice the size of the sub-loop: $4$ elements. Notice the size of the whole clock: $12$ elements. $4$ divides $12$ cleanly ($12 / 4 = 3$). Could you ever create a sub-loop of size 5 on a 12-hour clock? Impossible! By Lagrange's Theorem, the size of any subgroup must divide the size of the parent group with zero remainder.

💻 Bridging to Computer Science: Diffie-Hellman Key Exchange & PRNGs

In computer science:

• Diffie-Hellman Key Exchange: Relies on large cyclic groups $(\mathbb{Z}_p^*, \times)$ where calculating discrete logarithms $g^x \equiv y \pmod p$ is computationally intractable.
• Linear Congruential Generators (LCGs): Pseudo-random number generators ($X_{n+1} = (aX_n + c) \bmod m$) require maximal period multipliers that act as full-cycle generators.
• Coset Codes & Error Detection: Linear block codes (Hamming codes) represent message words as subgroups whose cosets enable maximum-likelihood syndrome decoding.

📑Table of Contents

• 🌀 Cyclic Groups: Definition, Generators & Theorems
• 🔢 The Generator Counting Theorem (Euler's Totient)
• 🛡️ Subgroups & The One-Step Subgroup Test
• ⚖️ Lagrange's Theorem & Subgroup Lattices
  • Subgroup Lattices: Cyclic Group vs Klein 4-Group
• 🧮 Number of Non-Isomorphic Abelian Groups
• 📝 Step-by-Step Worked Examples
  • Example 1: Finding All Subgroups and Generators of (ℤ₁₂, +₁₂)
  • Example 2: Analyzing Non-Existence of Subgroups
• 🎯 Exam & Interview Pitfall Check

---

🌀 Cyclic Groups: Definition, Generators & Theorems

📖Definition 5.3: Cyclic Groupdefinition

A group $(G, *)$ is called cyclic if there exists an element $a \in G$ such that every element of $G$ can be expressed as an integer power (or multiple) of $a$:

$$G = \langle a \rangle = \{ a^k \mid k \in \mathbb{Z} \} \quad (\text{Multiplicative Notation})$$$$G = \langle a \rangle = \{ k \cdot a \mid k \in \mathbb{Z} \} \quad (\text{Additive Notation})$$

The element $a$ is called a generator of the cyclic group $G$.

• If $G = \langle a \rangle$ has finite order $n$, then: $$G = \{ a^0 = e, \; a^1, \; a^2, \; \dots, \; a^{n-1} \}$$
• The order of any generator equals the order of the group: $o(a) = \vert G \vert = n$.

★ Full Generator: ⟨1⟩

Generator ⟨1⟩ in (ℤ₆, +₆): Full Hamiltonian cycle of order 6.

✓ Subgroup: ⟨2⟩ = {0, 2, 4}

Subgroup ⟨2⟩ in (ℤ₆, +₆): Traces an inscribed triangle of order 3 dividing 6.

📐Theorem 5.2: Fundamental Theorems of Cyclic Groupstheorem

1. Every Cyclic Group is Abelian: If $G = \langle a \rangle$, let $x = a^r$ and $y = a^s$. Then: $$x * y = a^r * a^s = a^{r+s} = a^{s+r} = a^s * a^r = y * x$$ (Warning: The converse is false! The Klein 4-group $V_4$ is Abelian, but non-cyclic).
2. Inverse Generator Invariant: If element $a$ is a generator of $G$, then its inverse $a^{-1}$ is also a generator of $G$: $$\langle a \rangle = G \iff \langle a^{-1} \rangle = G$$
3. Prime Order Groups are Always Cyclic: Every group of prime order $p$ is strictly cyclic and therefore Abelian.
4. Order of Elements in Cyclic Groups: In a finite cyclic group $G = \langle a \rangle$ of order $n$, the order of any element $a^k$ is: $$o(a^k) = \frac{n}{\gcd(k, n)}$$

---

🔢 The Generator Counting Theorem (Euler's Totient)

How many generators does a finite cyclic group possess?

📐Theorem 5.3: Generator Invariant & Euler's Totient Formulatheorem

Let $G = \langle a \rangle$ be a finite cyclic group of order $n$.

1. An element $a^k \in G$ is a generator of $G$ if and only if $k$ is coprime to $n$: $$\gcd(k, n) = 1$$
2. The total number of generators of a cyclic group of order $n$ is given by Euler's Totient Function $\phi(n)$: $$\text{Number of Generators} = \phi(n) = \frac{n(P_1 - 1)(P_2 - 1)\cdots(P_k - 1)}{P_1 P_2 \cdots P_k}$$ where $n = P_1^{a_1} P_2^{a_2} \cdots P_k^{a_k}$ is the prime factorization of $n$.

Standard Calculations:

• For $\vert G \vert = 8 = 2^3$: Unique prime factor is $2$. $$\phi(8) = \frac{8(2 - 1)}{2} = 4 \quad (\text{Generators: } \{1, 3, 5, 7\})$$
• For $\vert G \vert = 12 = 2^2 \times 3^1$: Unique prime factors are $2, 3$. $$\phi(12) = \frac{12(2 - 1)(3 - 1)}{2 \times 3} = \frac{12 \times 1 \times 2}{6} = 4 \quad (\text{Generators: } \{1, 5, 7, 11\})$$
• Infinite Cyclic Group Invariant: An infinite cyclic group (such as $(\mathbb{Z}, +)$) has exactly two generators: $1$ and $-1$.

---

🛡️ Subgroups & The One-Step Subgroup Test

📖Definition 5.4: Subgroupdefinition

Let $(G, *)$ be a group. A subset $H \subseteq G$ is called a subgroup of $G$ (denoted $H \le G$) if $H$ itself forms a group under the same binary operation $*$.

• Trivial Subgroups: Every group $G$ has at least two trivial subgroups:
  1. The identity subgroup $\{e\}$.
  2. The improper subgroup $G$ itself.
• Any subgroup $H$ such that $H \neq \{e\}$ and $H \neq G$ is a proper, non-trivial subgroup.

Architecture Flow

The One-Step Subgroup Test Pipeline

Minimal necessary and sufficient condition to verify if a subset H is a valid subgroup

🔍Step 1

Non-Emptiness & Identity

Verify that H ≠ ∅ (typically by confirming e ∈ H).

→

Pass: Non-Empty

⚡Step 2

Inverse-Product Closure

For all a, b ∈ H, verify that a * b⁻¹ ∈ H (or a - b ∈ H in additive notation).

→

Pass: One-Step Test Satisfied

🛡️Result

Certified Subgroup H ≤ G

H is guaranteed to satisfy Closure, Associativity, Identity, and Inverses.

📐Theorem 5.4: Fundamental Subgroup Properties (GATE Essentials)theorem

1. Shared Identity Element: The identity element of a subgroup $H$ is strictly identical to the identity element of the parent group $G$: $e_H = e_G$.
2. Intersection of Subgroups: If $H_1 \le G$ and $H_2 \le G$, their intersection $H_1 \cap H_2$ is ALWAYS a subgroup of $G$.
3. Union of Subgroups: The union $H_1 \cup H_2$ is a subgroup of $G$ if and only if one subgroup is entirely contained within the other: $$H_1 \cup H_2 \le G \iff (H_1 \subseteq H_2 \quad \text{or} \quad H_2 \subseteq H_1)$$ (Example: In $(\mathbb{Z}, +)$, $2\mathbb{Z} \cup 3\mathbb{Z}$ is NOT a subgroup because $2 + 3 = 5 \notin 2\mathbb{Z} \cup 3\mathbb{Z}$).

---

⚖️ Lagrange's Theorem & Subgroup Lattices

📐Theorem 5.5: Lagrange's Theoremtheorem

If $G$ is a finite group and $H$ is a subgroup of $G$, then the order of $H$ divides the order of $G$:

$$\vert H \vert \text{ divides } \vert G \vert \quad \iff \quad \frac{\vert G \vert}{\vert H \vert} = k \in \mathbb{Z}^+$$

The positive integer $[G : H] = \frac{\vert G \vert}{\vert H \vert}$ is called the Index of $H$ in $G$, representing the exact number of distinct cosets of $H$ in $G$.

How Lagrange's Theorem Partitions the Parent Group G

Coset decomposition proving why subgroup order must divide group order

1

Form the Cosets of H

Equivalence Classes

For any element g ∈ G, construct the left coset gH = { g * h | h ∈ H }.

2

Equal Cardinality Invariant

Bijection

Every coset gH has EXACTLY the same number of elements as H: |gH| = |H|.

3

Mutual Disjointness

Partition

Any two cosets are either completely identical or completely disjoint: g₁H ∩ g₂H = ∅.

4

Sum of Slices Equals |G|

Divisibility

G is the union of k mutually disjoint cosets, each of size |H|. Therefore: |G| = k × |H|.

Subgroup Lattices: Cyclic Group vs Klein 4-Group

The set of all subgroups of a group $G$ ordered by set inclusion forms a complete Lattice (the Subgroup Lattice):

★ Subgroup Lattice (ℤ₁₂)

Subgroups of (ℤ₁₂, +₁₂) ordered by inclusion: Isomorphic to D₁₂.

★ Subgroup Lattice (V₄)

Subgroups of Klein 4-Group V₄: Forms the diamond lattice M₃.

• In the cyclic group $(\mathbb{Z}_{12}, +_{12})$, there exists exactly one subgroup for each positive divisor of $12$ ($\tau(12) = 6$ subgroups), yielding the divisibility lattice $D_{12}$.
• In the non-cyclic Klein 4-group $V_4$, there are 3 distinct subgroups of order 2, forming the non-distributive diamond lattice $M_3$!

---

🧮 Number of Non-Isomorphic Abelian Groups

📐Theorem 5.6: Counting Non-Isomorphic Abelian Groups via Integer Partitionstheorem

By the Fundamental Theorem of Finite Abelian Groups, any finite Abelian group can be uniquely decomposed into a direct product of cyclic groups of prime-power orders.

1. If $\vert G \vert = p^k$ where $p$ is a prime: $$\text{Number of Non-Isomorphic Abelian Groups} = P(k)$$ where $P(k)$ is the number of integer partitions of $k$.
2. For composite order with prime factorization $\vert G \vert = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$: $$\text{Total Non-Isomorphic Abelian Groups} = P(k_1) \times P(k_2) \times \dots \times P(k_m)$$

Worked Examples:

• Order $4 = 2^2$: $k = 2$. Partitions of 2 are $\{2\}$ and $\{1+1\}$. $\implies P(2) = 2$ groups: $\mathbb{Z}_4$ and $\mathbb{Z}_2 \times \mathbb{Z}_2$ ($V_4$).
• Order $8 = 2^3$: $k = 3$. Partitions of 3 are $\{3\}, \{2+1\}, \{1+1+1\}$. $\implies P(3) = 3$ groups: $\mathbb{Z}_8$, $\mathbb{Z}_4 \times \mathbb{Z}_2$, and $\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2$.
• Order $72 = 2^3 \times 3^2$: $k_1 = 3, k_2 = 2$. $\implies P(3) \times P(2) = 3 \times 2 = 6$ non-isomorphic Abelian groups!

---

📝 Step-by-Step Worked Examples

Example 1: Finding All Subgroups and Generators of (ℤ₁₂, +₁₂)

Problem Statement: Consider the additive cyclic group $(\mathbb{Z}_{12}, +_{12})$.

1. How many generators does $\mathbb{Z}_{12}$ have, and what are they?
2. List all possible orders of subgroups allowed by Lagrange's Theorem.
3. Find the generator and elements of the subgroup of order 4.

Step-by-Step Solution:

1. Step 1: Find All Generators

   • The order of the group is $n = 12$.
   • By Theorem 5.3, the number of generators is $\phi(12)$: $$12 = 2^2 \times 3^1 \implies \phi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4$$
   • The generators are elements $k \in \{0, 1, 2, \dots, 11\}$ with $\gcd(k, 12) = 1$: $$\text{Generators} = \{1, 5, 7, 11\}$$

2. Step 2: Subgroup Orders Allowed by Lagrange's Theorem

   • Any subgroup order must be a positive divisor of $12$.
   • Divisors of $12$ are: $$\{1, 2, 3, 4, 6, 12\}$$
   • Since $\mathbb{Z}_{12}$ is cyclic, for every divisor $d \mid 12$, there exists a unique subgroup of order $d$!

3. Step 3: Subgroup of Order 4

   • We want a subgroup $H$ with $\vert H \vert = 4$.
   • In an additive cyclic group $\mathbb{Z}_n$, the unique subgroup of order $d$ is generated by $n / d$: $$\text{Generator} = \frac{12}{4} = 3$$
   • Generating multiples of 3: $$H = \langle 3 \rangle = \{0, 3, 6, 9\}$$
   • Verification: $\vert H \vert = 4$, and $(3 + 9) \bmod 12 = 0 \in H$. Clean!

Key Takeaway: In any finite cyclic group of order $n$, there exists exactly one subgroup of order $d$ for each divisor $d \mid n$, generated by $a^{n/d}$.

---

Example 2: Analyzing Non-Existence of Subgroups

Problem Statement: A group $G$ has order $\vert G \vert = 35$.

1. Can $G$ have a subgroup of order $6$?
2. Can $G$ have an element of order $7$?
3. Can $G$ have an element of order $4$?

Step-by-Step Solution:

1. Subgroup of Order 6:

   • By Lagrange's Theorem, the order of any subgroup $H$ must divide $\vert G \vert = 35$.
   • The positive divisors of $35$ are $\{1, 5, 7, 35\}$.
   • Since $6$ does not divide $35$ ($35 / 6 \approx 5.83 \notin \mathbb{Z}$), NO subgroup of order 6 can possibly exist!

2. Element of Order 7:

   • By Cauchy's Theorem, if a prime $p$ divides $\vert G \vert$, $G$ must contain an element of order $p$.
   • Since $7 \mid 35$, YES, $G$ is guaranteed to have elements of order 7.

3. Element of Order 4:

   • By Lagrange's Corollary, the order of any element must divide the group order $\vert G \vert = 35$.
   • Since $4$ does not divide $35$, NO element of order 4 can exist in $G$!

Key Takeaway: Lagrange's Theorem acts as a strict negative filter: if a number does not divide $\vert G \vert$, neither a subgroup nor an element of that order can exist!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Is the converse of Lagrange's Theorem always true? (i.e., if $d \mid \vert G \vert$, must $G$ have a subgroup of order $d$?) Key Focus Points: No! The converse of Lagrange's Theorem is FALSE in general. The smallest counterexample is the Alternating group $A_4$ (even permutations of 4 items), which has order $\vert A_4 \vert = 12$. Even though $6$ divides $12$, $A_4$ has no subgroup of order 6! (Note: The converse is true if $G$ is Abelian or cyclic).

Question 2: If a group has order 17, how many subgroups does it have? Key Focus Points: Since $17$ is prime, by the Prime Order Theorem, $G$ is cyclic and has only 2 subgroups: the trivial identity subgroup $\{e\}$ of order 1, and $G$ itself of order 17. No proper non-trivial subgroups can exist!

Question 3: Can the union of two subgroups $\{0, 2, 4\}$ and $\{0, 3\}$ in $(\mathbb{Z}_6, +_6)$ form a subgroup? Key Focus Points: No! The union is $\{0, 2, 3, 4\}$. It has cardinality 4, which does not divide $\vert \mathbb{Z}_6 \vert = 6$ (violating Lagrange's Theorem). Moreover, $2 + 3 = 5 \notin \{0, 2, 3, 4\}$, violating closure! The union of two subgroups is a subgroup if and only if one is contained in the other.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Assuming all Abelian groups are cyclic Why it fails: All cyclic groups are Abelian, but the converse is false! The Klein 4-group $V_4$ and $(\mathbb{Z}_2 \times \mathbb{Z}_2, +)$ are Abelian of order 4, but have no element of order 4, so they are not cyclic.

Trap 2: Believing $\phi(n)$ gives the number of subgroups Why it fails: $\phi(n)$ gives the number of generators of a cyclic group of order $n$, NOT the number of subgroups. The number of subgroups of a cyclic group of order $n$ equals the number of divisors $\tau(n)$ of $n$!

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic5.1 Algebraic Hierarchy: Semigroups, Monoids, Groups & Abelian GroupsNext Topic →5.3 Cosets, Normal Subgroups, Rings, Integral Domains & Fields