# Lecture 11: Basic Group Theory Source: https://www.youtube.com/watch?v=hUtdHAeyY6Y Recap page: https://rapidrecap.app/video/hUtdHAeyY6Y Generated: 2025-12-17T16:37:07.504+00:00 --- ## Quick Overview The lecture introduces the foundational definition of a group in abstract algebra, comprising a set and a binary operation satisfying closure, associativity, identity existence, and inverse existence, and demonstrates how this abstraction formalizes concepts like multiplicative inverses in modular arithmetic, leading to the proof of Lagrange's theorem which states that the order of a subgroup must divide the order of a finite group, which in turn is used to prove Fermat's Little Theorem and Euler's Totient Theorem. **Key Points:** - A group is formally defined as a pair (G, star) satisfying closure (a * b is in G), associativity ((a * b) * c = a * (b * c)), identity existence (e such that a * e = e * a = a), and inverse existence (a inverse such that a * a inverse = a inverse * a = e); if a * b = b * a, the group is called abelian. - The set of non-zero elements of Zn under multiplication forms a group if and only if n is prime, a result derived from the fact that every non-zero element has a multiplicative inverse when GCD(a, n) = 1. - The order of a finite group G, denoted |G|, is the number of elements, and Lagrange's theorem states that if H is a subgroup of G, then |H| divides |G|. - Lagrange's theorem is proven by partitioning G into disjoint cosets of H (xH), showing each coset has size |H| using the existence of x inverse, and showing that any intersection between two cosets implies the second element belongs to the first coset, forcing the union to be disjoint. - Fermat's Little Theorem, stating a^(p-1) ≡ 1 (mod p) for prime p and p not dividing a, is proven by defining k as the smallest integer such that a^k ≡ 1 (mod p), establishing that the powers of a form a subgroup of order k, and applying Lagrange's theorem that k divides |Zp*| = p - 1. - Euler's Theorem extends Fermat's result to composite modulus m=pq (p, q distinct primes) for elements a where GCD(a, m) = 1, stating a^(phi(m)) ≡ 1 (mod m), where phi(m) = (p-1)(q-1) is the order of the multiplicative group Zm*. **Context:** The lecture continues an exploration of algebra, building upon the previous discussion of modular arithmetic, the Euclidean algorithm, and the existence of multiplicative inverses. The speaker, Ankur Moitra, introduces group theory as a powerful abstraction to formalize these algebraic structures. The core focus of the session is defining what constitutes a group and subsequently proving Lagrange's theorem, which connects the sizes of groups and their subgroups, leading directly to applications in number theory like Fermat's Little Theorem. ## Detailed Analysis The lecture rigorously defines an algebraic structure called a group, characterized by a set G and a binary operation * that must satisfy closure, associativity, the existence of an identity element (e), and the existence of an inverse for every element. Groups where the operation is commutative are termed abelian. The speaker illustrates this by confirming the integers under addition form an abelian group but integers under multiplication do not because inverses (like 1/2 for 2) may not exist in the set. A key result is that Zn \ {0} under multiplication forms a group if and only if n is prime, because this condition guarantees the existence of multiplicative inverses for all non-zero elements, which is contingent on GCD(a, n) = 1. The concept of the order of a group, |G|, is introduced, followed by the crucial Lagrange's Theorem: for a finite group G and a subgroup H, |H| divides |G|. The proof involves partitioning G into disjoint left cosets (xH) of the subgroup H, demonstrating each coset has the same size as H, and showing that any apparent overlap between cosets forces the elements to belong to an already established coset, thus proving the partition is disjoint and covering G exactly |G|/|H| times. This structural result is immediately applied to prove Fermat's Little Theorem by examining the subgroup generated by powers of an element 'a' modulo a prime p, showing its order k must divide p-1. Finally, Euler's Theorem is presented, extending the result to composite moduli by using the order of the multiplicative group Zm*, calculated as |Zm*| = (p-1)(q-1) when m=pq, which is the exponent required for a^exponent ≡ 1 (mod m). The lecture concludes by briefly defining a field as a set with two operations (addition and multiplication) satisfying group axioms for both (with 0 excluded for multiplication) plus the distributive law, noting that polynomials over a field have at most d roots for degree d. ### Group Definition Axioms - Closure is required so a * b remains in G - Associativity must hold for triples - Identity element e must exist - Inverse element a inverse must exist for all a - Commutativity makes it an abelian group. ### Examples and Non-Examples - Integers under addition form an abelian group with identity 0 and inverse -a - Integers under multiplication fail because 2 does not have an inverse (1/2) in the set - Rationals minus 0 under multiplication form a group. ### Modular Arithmetic Groups - Zn with addition is a group - Zn \ {0} with multiplication is a group if and only if n is prime, because this ensures GCD(a, n) = 1 guarantees an inverse. ### Subgroups and Cosets - H is a subgroup of G if H is a group under the same operation, requiring stronger closure within H and that inverses for elements in H remain in H - Cosets are translates of H, defined as xH = {x * y - y in H}. ### Proof of Lagrange's Theorem - G must be partitioned into disjoint cosets x1H U x2H U ... U xkH - Property 1 (all cosets have size - H - ) holds because x*h1 = x*h2 implies h1 = h2 via left multiplication by x inverse - Property 2 (cosets are disjoint) holds because assuming an intersection forces the element xj from a later coset to belong to an earlier coset xiH, contradicting the construction method. ### Application to Fermat's Little Theorem - If p is prime and GCD(a, p) = 1, then a^(p-1) ≡ 1 (mod p) - The order k of the subgroup generated by powers of a must divide - Zp* - = p - 1 by Lagrange's theorem, meaning p-1 = c*k, so a^(p-1) = (a^k)^c ≡ 1^c ≡ 1 (mod p). ### Euler's Theorem and RSA Hint - For composite m=pq (p, q distinct primes) and GCD(a, m) = 1, a^((p-1)(q-1)) ≡ 1 (mod m) - The exponent (p-1)(q-1) is the order of the multiplicative group Zm*, which is used in RSA encryption. ### Fields and Polynomial Roots - A field F has two operations (addition, multiplication) where (F, +) and (F \ {0}, *) are both abelian groups, linked by the distributive law - A polynomial of degree d over a field F has at most d roots in F.