Lecture 11: Basic Group Theory

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.