Cosets, Index and Lagrange's Theorem

Given: A group $G$, a subgroup $H\le G$, and elements $a,b,x\in G$.

The left coset $aH$ is $\{ah:h\in H\}$, and the right coset $Ha$ is $\{ha:h\in H\}$ (Left and right cosets $gH$ and $Hg$ of a subgroup).

A subgroup contains the identity and is closed under products and inverses (Subgroup).

In a group, $(uv{)}^{-1}=v^{-1}{u}^{-1}$ and $(u^{-1}{)}^{-1}=u$ (In a group $e^{-1}=e$, $(g^{-1}{)}^{-1}=g$ and $(gh{)}^{-1}=h^{-1}{g}^{-1}$, the order of the last product being essential).

Left and right cancellation hold in every group (Cancellation in a group: $gx=gy$ or $xg=yg$ forces $x=y$; equivalently left and right translation by $g$ are bijections of $G$, so $gx=h$ and $xg=h$ each have exactly one solution, Group and abelian group).

Given: A group $G$ and a subgroup $H\le G$.

A relation is an equivalence relation when it is reflexive, symmetric and transitive (Equivalence relation, equivalence class, and the quotient set $A\mathrm{/}\sim$).

The equivalence classes of an equivalence relation on a set are nonempty, cover the set and are pairwise equal or disjoint (The equivalence classes of an equivalence relation are nonempty, cover $A$, and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation).

For $a,b\in G$, $b\in aH$ if and only if $a^{-1}b\in H$, and $aH=bH$ if and only if $a^{-1}b\in H$ ($x\in aH$ iff $a^{-1}x\in H$, and $aH=bH$ iff $a^{-1}b\in H$).

Because $H\le G$, it contains the identity and is closed under inverses and products (Subgroup).

Given: A group $G$, a subgroup $H\le G$, and $g\in G$.

The cosets are $gH=\{gh:h\in H\}$ and $Hg=\{hg:h\in H\}$ (Left and right cosets $gH$ and $Hg$ of a subgroup).

A map is bijective when it is injective and surjective; two sets are equinumerous when a bijection between them exists (Injection, surjection, bijection, Equinumerous sets, $A\approx B$ and $A⪯B$).

Left and right cancellation hold in a group (Cancellation in a group: $gx=gy$ or $xg=yg$ forces $x=y$; equivalently left and right translation by $g$ are bijections of $G$, so $gx=h$ and $xg=h$ each have exactly one solution).

Given: A group $G$ and a subgroup $H\le G$.

For left cosets, $gH=kH$ if and only if $g^{-1}k\in H$; for right cosets, $Hg=Hk$ if and only if $g{k}^{-1}\in H$ ($x\in aH$ iff $a^{-1}x\in H$, and $aH=bH$ iff $a^{-1}b\in H$).

In a group, $(uv{)}^{-1}=v^{-1}{u}^{-1}$ and $(u^{-1}{)}^{-1}=u$ (In a group $e^{-1}=e$, $(g^{-1}{)}^{-1}=g$ and $(gh{)}^{-1}=h^{-1}{g}^{-1}$, the order of the last product being essential).

A subgroup is closed under inverses (Subgroup).

A map with a two-sided inverse is a bijection (Injection, surjection, bijection, Equinumerous sets, $A\approx B$ and $A⪯B$).

Given: A finite group $G$ and a subgroup $H\le G$.

Every subset of a finite set is finite (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$).

The power set of a finite set is finite ($\mid \mathcal{P}(A)\mid =2^{\mid A\mid }$ for finite $A$).

Every left or right coset of $H$ is equinumerous with $H$ (Every left or right coset of $H$ is equinumerous with $H$).

A bijection transports finiteness and finite cardinality (The cardinality $\mid A\mid$ of a finite set).

The coset set is $G\mathrm{/}H=\{gH:g\in G\}$, and its finite cardinality is the index (The coset set $G\mathrm{/}H$ and the index $[G:H]$ of a subgroup, The left cosets of a subgroup partition the group).

Given: A finite group $G$ and a subgroup $H\le G$.

The distinct left cosets of $H$ partition $G$ (The left cosets of a subgroup partition the group).

The subgroup, every coset, and $G\mathrm{/}H$ are finite; every coset has cardinality $\mathrm{\mid }H\mathrm{\mid }$ and $\mathrm{\mid }G\mathrm{/}H\mathrm{\mid }=[G:H]$ (In a finite group, the subgroup, every coset and the set of cosets are finite, Every left or right coset of $H$ is equinumerous with $H$, The coset set $G\mathrm{/}H$ and the index $[G:H]$ of a subgroup).

For a finite partition $A={⨆}_{i\in I}{A}_i$, one has $\mathrm{\mid }A\mathrm{\mid }={\sum }_{i\in I}\mathrm{\mid }{A}_i\mathrm{\mid }$; if every summand has the same value $c$, then ${\sum }_{i\in I}c=\mathrm{\mid }I\mathrm{\mid }c$ (The sum rule: a finite disjoint union is finite with $\mid A\cup B\mid =\mid A\mid +\mid B\mid$ and $\mid {\bigcup }_{i\in I}{A}_i\mid ={\sum }_{i\in I}\mid A_i\mid$, and a sum over a finite index set splits along a partition, The sum ${\sum }_{i\in S}{a}_i$ over a finite index set, and its product form).

The order $\mathrm{\mid }G\mathrm{\mid }$ of a finite group is the unique natural equinumerous with its underlying set, hence agrees with finite cardinality (The order $\mathrm{\mid }G\mathrm{\mid }$ of a finite group and the order $\mathrm{ord}(g)$ of an element, with $\mathrm{ord}(g)=\mathrm{\infty }$ when no positive power of $g$ is the identity, The cardinality $\mid A\mid$ of a finite set).

The embedding $\iota$ preserves multiplication, and $d\mid a$ in $\mathbb{Z}$ means $a=dq$ for some integer $q$ (The naturals embed in the integers, Divisibility in $\mathbb{Z}$: $d\mid a$ when $a=dq$ for some integer $q$).

Given: A finite group $G$ and an element $g\in G$.

The generated set $⟨g⟩$ is a subgroup of $G$ and equals the set of integer powers of $g$ (The subgroup $⟨S⟩$ generated by a subset, the cyclic subgroup $⟨g⟩$, and cyclic groups, $⟨g⟩=\{g^n:n\in \mathbb{Z}\}$, and every cyclic group is abelian).

If $g$ has finite order, then $⟨g⟩$ is finite and $\mathrm{\mid }⟨g⟩\mathrm{\mid }=\mathrm{ord}(g)$; every element of a finite group has finite order (If $\mathrm{ord}(g)=n$ then $g^k=e$ iff $k$ is an integer multiple of $n$, the powers $g^0,\dots ,g^{n-1}$ are distinct, and $⟨g⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^j=g^k$ only for $j=k$, The order $\mathrm{\mid }G\mathrm{\mid }$ of a finite group and the order $\mathrm{ord}(g)$ of an element, with $\mathrm{ord}(g)=\mathrm{\infty }$ when no positive power of $g$ is the identity).

Lagrange's theorem gives $\mathrm{\mid }G\mathrm{\mid }=[G:H]\mathrm{\mid }H\mathrm{\mid }$ for every subgroup $H$ of a finite group and consequently $\iota (\mathrm{\mid }H\mathrm{\mid })\mid \iota (\mathrm{\mid }G\mathrm{\mid })$ (Lagrange's theorem: $\mathrm{\mid }G\mathrm{\mid }=[G:H]\mathrm{\mid }H\mathrm{\mid }$ for every subgroup $H$ of a finite group $G$, Divisibility in $\mathbb{Z}$: $d\mid a$ when $a=dq$ for some integer $q$, The naturals embed in the integers).

Given: A finite group $G$ with identity $e$ and an element $g\in G$.

The order $n=\mathrm{ord}(g)$ is finite and $\iota (n)$ divides $\iota (\mathrm{\mid }G\mathrm{\mid })$ (The order of every element of a finite group divides the order of the group, The order $\mathrm{\mid }G\mathrm{\mid }$ of a finite group and the order $\mathrm{ord}(g)$ of an element, with $\mathrm{ord}(g)=\mathrm{\infty }$ when no positive power of $g$ is the identity, The naturals embed in the integers).

If $\mathrm{ord}(g)=n$, then for every integer $k$, $g^k=e$ if and only if $n\mid k$ (If $\mathrm{ord}(g)=n$ then $g^k=e$ iff $k$ is an integer multiple of $n$, the powers $g^0,\dots ,g^{n-1}$ are distinct, and $⟨g⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^j=g^k$ only for $j=k$, Powers $g^n$: natural exponents in a monoid and integer exponents in a group, with $g^0=e$, Exponent laws in a group: $g^{m+n}=g^m{g}^n$ and $(g^m{)}^n=g^{mn}$ for all $m,n\in \mathbb{Z}$, and $(gh{)}^n=g^n{h}^n$ when $g$ and $h$ commute).

Given: A finite group $G$ with identity $e$, with $\iota (\mathrm{\mid }G\mathrm{\mid })$ prime, and an element $g\in G$ with $g\mathrm{\ne }e$.

A prime integer $p$ satisfies $p>1$, and every positive divisor of $p$ is $1$ or $p$ (Prime and composite integers: $p$ is prime when $p>1$ and its only positive divisors are $1$ and $p$).

The natural $\mathrm{ord}(g)$ is positive, equals $1$ exactly when $g=e$, and its image in $\mathbb{Z}$ divides $\iota (\mathrm{\mid }G\mathrm{\mid })$; the embedding $\iota :\mathbb{N}\to \mathbb{Z}$ is injective and preserves order (The order $\mathrm{\mid }G\mathrm{\mid }$ of a finite group and the order $\mathrm{ord}(g)$ of an element, with $\mathrm{ord}(g)=\mathrm{\infty }$ when no positive power of $g$ is the identity, The order of every element of a finite group divides the order of the group, The naturals embed in the integers).

The cyclic subgroup $⟨g⟩$ is a subgroup with $\mathrm{\mid }⟨g⟩\mathrm{\mid }=\mathrm{ord}(g)$ (The subgroup $⟨S⟩$ generated by a subset, the cyclic subgroup $⟨g⟩$, and cyclic groups, $⟨g⟩=\{g^n:n\in \mathbb{Z}\}$, and every cyclic group is abelian, If $\mathrm{ord}(g)=n$ then $g^k=e$ iff $k$ is an integer multiple of $n$, the powers $g^0,\dots ,g^{n-1}$ are distinct, and $⟨g⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^j=g^k$ only for $j=k$).

If $A\subseteq B$ are finite and $\mathrm{\mid }A\mathrm{\mid }=\mathrm{\mid }B\mathrm{\mid }$, then $A=B$ (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$).

If a finite set $G$ contains $e$ and $\mathrm{\mid }G\mathrm{\mid }\mathrm{\ne }1$, then some element of $G$ differs from $e$: otherwise $G=\{e\}$, whose cardinality is $1$ (The cardinality $\mid A\mid$ of a finite set).

Given: A finite group $G$ and subgroups $K\le H\le G$.

Lagrange's theorem gives $\mathrm{\mid }B\mathrm{\mid }=[B:A]\mathrm{\mid }A\mathrm{\mid }$ whenever $A\le B$ and $B$ is finite (Lagrange's theorem: $\mathrm{\mid }G\mathrm{\mid }=[G:H]\mathrm{\mid }H\mathrm{\mid }$ for every subgroup $H$ of a finite group $G$, The coset set $G\mathrm{/}H$ and the index $[G:H]$ of a subgroup, The order $\mathrm{\mid }G\mathrm{\mid }$ of a finite group and the order $\mathrm{ord}(g)$ of an element, with $\mathrm{ord}(g)=\mathrm{\infty }$ when no positive power of $g$ is the identity).

Every subgroup contains the identity; hence its underlying set is nonempty. Also, if $K\le H\le G$, then $K\le G$: one has $K\subseteq H\subseteq G$, and the identity, product, and inverse conditions for $K$ are the same inherited operations in $H$ and $G$ (Subgroup).

Every subset of a finite set is finite (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$).

Natural multiplication is associative, and $xz=yz$ with $z\mathrm{\ne }0$ implies $x=y$ (Multiplication is associative, Cancellation for multiplication by a nonzero factor).

Given: A group $G$ and a subgroup $H\le G$.

The coset set is $G\mathrm{/}H=\{gH:g\in G\}$. Its index is its finite cardinality when the coset set is finite and is the non-natural symbol $\mathrm{\infty }$ otherwise; hence $[G:H]=1$ says that $G\mathrm{/}H$ is finite of cardinality $1$ (The coset set $G\mathrm{/}H$ and the index $[G:H]$ of a subgroup, Left and right cosets $gH$ and $Hg$ of a subgroup).

The cosets partition $G$, and $gH=H$ exactly when $g\in H$ (The left cosets of a subgroup partition the group, $x\in aH$ iff $a^{-1}x\in H$, and $aH=bH$ iff $a^{-1}b\in H$).

A finite set has cardinality $1$ exactly when it is a singleton: a bijection to $1=\{0\}$ has one fibre and hence one element, while the unique map from a singleton to $1$ is a bijection (The cardinality $\mid A\mid$ of a finite set).

Given: A positive integer $n$ and an integer $a$ with $\gcd (a,n)=1$.

The unit group $(\mathbb{Z}\mathrm{/}n{)}^{\times }$ is finite of order $\phi (n)$ and has identity $[1{]}_n$ (The unit group $(\mathbb{Z}\mathrm{/}n{)}^{\times }$ and Euler's totient $\phi (n)=\mid (\mathbb{Z}\mathrm{/}n{)}^{\times }\mid$ for $n\ge 1$).

The class $[a{]}_n$ is a unit if and only if $\gcd (a,n)=1$ (For $n\ge 1$, $[a{]}_n$ is a unit if and only if $\gcd (a,n)=1$).

Every element $u$ of a finite group satisfies $u^{\mathrm{\mid }G\mathrm{\mid }}=e$ ($g^{\mathrm{\mid }G\mathrm{\mid }}=e$ for every element $g$ of a finite group $G$, Powers $g^n$: natural exponents in a monoid and integer exponents in a group, with $g^0=e$).

Multiplication of residue classes satisfies $[x{]}_n[y{]}_n=[xy{]}_n$, so natural powers satisfy $[a{]}_n^k=[a^k{]}_n$; and $[x{]}_n=[y{]}_n$ exactly when $x\equiv y(\mathrm{m}\mathrm{o}\mathrm{d}n)$ (Addition and multiplication on $\mathbb{Z}\mathrm{/}n$ by $[a{]}_n+[b{]}_n=[a+b{]}_n$ and $[a{]}_n[b{]}_n=[ab{]}_n$, The congruence class $[a{]}_n$ and the quotient set $\mathbb{Z}\mathrm{/}n$, Congruence modulo an integer: $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$ when $n\mid (a-b)$, including the moduli $0$ and $1$, Congruent integers may be added, subtracted and multiplied: representative changes preserve both arithmetic operations).

Given: A prime integer $p$ and an integer $a$.

A prime satisfies $p>1$, and $p\nmid a$ implies $\gcd (p,a)=1$, hence $\gcd (a,p)=1$ by symmetry of the gcd (Prime and composite integers: $p$ is prime when $p>1$ and its only positive divisors are $1$ and $p$, For a prime $p$ and any integer $a$, $\gcd (p,a)$ is $p$ when $p\mid a$ and $1$ otherwise; so $p\nmid a$ makes $p$ and $a$ coprime, $\gcd$ is symmetric and unchanged by signs: $\gcd (a,b)=\gcd (b,a)=\gcd (\mathrm{\mid }a\mathrm{\mid },\mathrm{\mid }b\mathrm{\mid })$; moreover $\gcd (a,0)=\mathrm{\mid }a\mathrm{\mid }$, $\gcd (a,1)=1$, $\gcd (a,a)=\mathrm{\mid }a\mathrm{\mid }$, and $\gcd (a,b)\ge 1$ unless $a=b=0$).

Euler's theorem gives $a^{\phi (p)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$ when $\gcd (a,p)=1$, and $\phi (p)=p-1$ for prime $p$ (Euler's theorem: if $n\ge 1$ and $\gcd (a,n)=1$, then $a^{\phi (n)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$, $\phi (1)=1$, and $\phi (p)=p-1$ for every prime $p$).

Congruence is preserved by multiplication, and $p\mid x$ is equivalent to $x\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$ (Congruent integers may be added, subtracted and multiplied: representative changes preserve both arithmetic operations, Congruence modulo an integer: $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$ when $n\mid (a-b)$, including the moduli $0$ and $1$, Divisibility in $\mathbb{Z}$: $d\mid a$ when $a=dq$ for some integer $q$).

Integer powers satisfy $a^p=a^{p-1}a$ for the positive exponent $p$ (Powers $g^n$: natural exponents in a monoid and integer exponents in a group, with $g^0=e$, Exponent laws in a group: $g^{m+n}=g^m{g}^n$ and $(g^m{)}^n=g^{mn}$ for all $m,n\in \mathbb{Z}$, and $(gh{)}^n=g^n{h}^n$ when $g$ and $h$ commute).